算法-O(1)时间删除链表的指定结点

柔情只为你懂 2022-06-10 00:27 151阅读 0赞

题目：给定一个链表的头指针和一个结点的指针，定义一个函数在O(1)时间删除该结点。链表结点与函数的定义如下：

struct ListNode
    {
      int value;
      ListNode *next;
    };

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

**解题思路：**  
首先，乍一看这个名字而不看题目要求的话，这是功能是不可能在O(1)时间完成的，我们在之前讨论过关于[单链表插入与删除][Link 1]的问题，链表的性质决定了不可能在O(1)下完成。所以题目给了我们其他的内容：**要删除的结点的指针**。

那么按照之前[单链表删除][Link 2]的思想来考虑的话，可以完成这件事，假设要删除的结点为i，i的前一个结点为h，那么我们需要找到h，并把h的next指针变为i的next指针，并释放i。

h->next = i->next;
    free(i);

这样的话i就删除了，不贴图了，前面的博客都有。但是这个思路不满足题目要求，因为单链表只有一个指向next的指针，那么我们想找到h只能从头遍历，一旦出现遍历这个东西，显然时间复杂度就不会是O(1)。

那么借助i前面的结点h是不行了，我们可以考虑能不能借助i后面的结点j，因为链表找到后面的结点只需要一步。我们只需要把j的value赋值给i的value，那么问题就变得清晰了：  
要删除的结点变成了j，而i就是j前面的一个结点，而i是题目给的，不需要遍历得到。我们把问题从删除i找h，变换到了删除j找i上。

![这里写图片描述][SouthEast]

但是仅仅上面的内容还不够全面，因为我们利用了i的下一个结点j完成这个任务，但是如果**i是尾结点呢**？  
这时我们还需要借助i的前一个结点h这种方法，即让h的next为null，并释放i。  
那么这样来看的话，又有了一个问题，**i如果没有h也没有j呢？**显然链表只有一个结点，而这个结点就是要删除的那个。

**代码实现**

void DeleteNode(ListNode** pListHead, ListNode* pToBeDeleted)
    {
        if(!pListHead || !pToBeDeleted)
            return;
    
        // 要删除的结点不是最后一个结点
        if(pToBeDeleted->next != NULL)
        {
            ListNode* pNext = pToBeDeleted->next;
            pToBeDeleted->value = pNext->value;
            pToBeDeleted->next = pNext->next;
    
            delete pNext;
            pNext = NULL;
        }
        // 链表只有一个结点，该结点就是要删除的结点
        else if(*pListHead == pToBeDeleted)
        {
            delete pToBeDeleted;
            pToBeDeleted = NULL;
            *pListHead = NULL;
        }
        // 链表有多个结点，要删除的结点是最后一个结点
        else
        {
            ListNode* pNode = *pListHead;
            while(pNode->next != pToBeDeleted)
            {
                pNode = pNode->next;            
            }
            pNode->next = NULL;
            delete pToBeDeleted;
            pToBeDeleted = NULL;
        }
    }

最后我们需要有两个注意的方法：  
（1）这种方法有一个假设条件，那就是i确实出现在链表中。  
（2）代码中还是出现了循环while，但是好在这个while在if里面，也就是遍历是有条件的，这个条件就是一个长度是n的链表，要删除的结点是尾结点，这个概率是1/n。除了这个之外，代码中其他部分的时间复杂度都是O(1)，所以平均来看的话，整体的时间复杂度满足O(1)。

[Link 1]: http://blog.csdn.net/chaipp0607/article/details/76524278
[Link 2]: http://blog.csdn.net/chaipp0607/article/details/76524278#t2
[SouthEast]: /images/20220610/e7ec032167a14761a4180e9fb1238d18.png