首页 > 代码库 > 剑指offer (13) O(1)时间删除单链表结点

剑指offer (13) O(1)时间删除单链表结点

2024-07-07 14:17:09   225人阅读

单链表删除结点操作：

方法一.  从链表的第一个结点开始遍历，顺序遍历到需删除结点的前一个结点，然后调整指针指向  T(n) = O(n)

方法二.  将 需删除结点i的下一个结点j(如果存在) 的值赋值给 需删除结点i，然后 删除结点j，这就相当于删除了结点i  T(n) = O(1)
 
  
 
 
需要注意以下几点：
1. 如果待删除结点为单链表尾结点，此时 其后无后继结点，这时需要 从链表开头开始 顺序遍历查找 待删除结点的前驱结点
2. 如果单链表就只有一个结点，且需要删除头结点，此时 需要修改链表头结点指针 指向 NULL
3. O(1)方法的前提是 待删除结点一定存在于 单链表之中
 
 1 void DeleteNode(ListNode** pListHead, ListNode* pToBeDeleted)
 2 {
 3     if(!pListHead || !pToBeDeleted)
 4         return;
 5 
 6     // 要删除的结点不是尾结点
 7     if(pToBeDeleted->m_pNext != NULL)
 8     {
 9         ListNode* pNext = pToBeDeleted->m_pNext;
10         pToBeDeleted->m_nValue = http://www.mamicode.com/pNext->m_nValue;
11         pToBeDeleted->m_pNext = pNext->m_pNext;
12  
13         delete pNext;
14         pNext = NULL;
15     }
16     // 链表只有一个结点，删除头结点（也是尾结点）
17     else if(*pListHead == pToBeDeleted)
18     {
19         delete pToBeDeleted;
20         pToBeDeleted = NULL;
21         *pListHead = NULL;
22     }
23     // 链表中有多个结点，删除尾结点
24     else
25     {
26         ListNode* pNode = *pListHead;
27         while(pNode->m_pNext != pToBeDeleted)
28         {
29             pNode = pNode->m_pNext;            
30         }
31  
32         pNode->m_pNext = NULL;
33         delete pToBeDeleted;
34         pToBeDeleted = NULL;
35     }
36 }

 


联系
我们