【劍指offer】面試題13:在O(1)時間刪除出鏈表結點


//題目:給定單向鏈表的頭指針和一個結點指針,定義一個函數在O(1)時間刪除該節點。
//鏈表結點與函數的定義
#include<iostream>
struct ListNode
{
int m_nValue;
ListNode* m_pNext;
};

void DeleteNode(ListNode** pHead, ListNode* pToBeDeleted);

void DeleteNode(ListNode** pHead, ListNode* pToBeDeleted)
{
if (pHead == NULL&*pHead == NULL)
{
return;
}

//要刪除的結點不是尾結點(包括頭結點但不是隻有一個結點)
if (pToBeDeleted->m_pNext != NULL)
{
//交換要刪除的結點的位置,轉換成刪除他的下一個結點
ListNode* pNext = pToBeDeleted->m_pNext;
pToBeDeleted->m_nValue = pNext->m_nValue;
pToBeDeleted->m_pNext = pNext->m_pNext;

delete pNext;
pNext = NULL;
}
//鏈表隻有一個結點,刪除頭結點(也是尾結點)
else if (*pHead == pToBeDeleted)
{
delete pToBeDeleted;
pToBeDeleted = NULL;
*pHead = NULL;

}

//鏈表有多個結點,刪除尾結點
else
{
ListNode*pNode = *pHead;
while (pNode->m_pNext != pToBeDeleted)//pNode為尾結點時,循環結束
{
pNode = pNode->m_pNext;
}
pNode->m_pNext = NULL;
delete pToBeDeleted;
pToBeDeleted = NULL;
}

}

分析一下時間效率:對於(n-1)個非尾結點時間復雜度為O(1),對於尾結點來說,時間復雜度為O(n),因此總的平均時間復雜度是[(n-1)O(1)+O(n)]/n=O(1);

0 個評論

要回覆文章請先登錄註冊