剑指offer - 删除链表的节点

题一

在O(1)时间内删除链表节点。给定单链表的头指针和一个节点指针，定义一个函数在O(1)时间内删除该节点。

链表节点与函数的定义如下

struct ListNode {
    int m_nValue;
    ListNode *m_pNext;
};

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

分析

思路1

在单向链表中删除一个节点，常规的做法无疑是从链表的头节点开始，顺序遍历查找要删除的节点，并在链表中删除该节点

如下图所示的链表中

272317431874277.jpg

我们想删除节点i，可以从链表的头节点a开始顺序遍历，发现节点h的m_pNext指向要删除的节点i，于是我们可以把节点h的m_pNext指向i的下一个节点，即节点j。指针调整之后，我们就可以安全地删除节点i并保证链表没有断开。如上图（b）所示，但是这种思路由于需要顺序查找，时间复杂度自然就是O(n)了。

之所以需要从头开始，是因为我们需要得到将被删除的节点的前一个节点。在单向链表中，节点中没有指向前一个节点的指针，所以只好从链表的头节点开始寻找。

思路2

其实可以很方便地得到要删除的节点的下一个节点。如果我们把下一个节点的内容复制到需要删除的节点上覆盖原有的内容，再把下一个节点删除，那是不是就相当于把当前需要删除的节点删除了？

还是前面的例子，我们要删除节点i，先把i的下一个节点j的内容复制到i，然后把i的指针指向节点j的下一个节点。此时再删除j，其效果刚好是把节点i删除了，如图（c）所示

上述思路还有一个问题：如果要删除的节点位于链表的尾部，那么它就没有下一个节点，怎么办？我们仍然从链表的头节点开始，顺序遍历得到该节点的前序节点，并完成删除操作

最后需要注意的是，如果链表只有一个节点，而我们又要删除链表的头节点（也是尾节点），那么，此时我们在删除节点之后，还需要把链表的头节点设置为nullptr。

代码实现

void DeleteNode(ListNode **pListHead, ListNode *pToBeDeleted)
{
   if (!pListHead || !pToBeDeleted)
       return;

    // 要删除的节点不是尾节点
    if (pToBeDeleted->m_pNext != nullptr)
    {
        ListNode *pNext = pToBeDeleted->m_pNext;
        pToBeDeleted->m_nValue = pNext->m_nValue;
        pToBeDeleted->m_pNext = pNext->m_pNext;

        delete pNext;
        pNext = nullptr;
    }
    else if (*pListHead == pToBeDeleted) // 链表只有一个节点，删除头节点（也是尾节点）
    {
        delete pToBeDeleted;
        pToBeDeleted = nullptr;
        *pListHead = nullptr;
    }
    else //链表中有多个节点，删除尾部节点
    {
        ListNode *pNode = *pListHead;
        while (pNode->m_pNext != pToBeDeleted) { // 顺序遍历，查找被删除节点
            pNode = pNode->m_pNext;
        }
        pNode->m_pNext = nullptr;
        delete pToBeDeleted;
        pToBeDeleted = nullptr;
    }
}

时间复杂度

对于n-1个非尾节点而言，我们可以在O(1)时间内把下一个节点的内存复制覆盖要删除的节点，并删除下一个节点；对于尾节点而言，由于仍然需要顺序查找，时间复杂度是O(n)。因此，总的平均复杂度是[(n-1)xO(1)+O(n)]/n，结果还是O(1)

但是注意：上述代码仍然是不完美的，因为它基于一个假设：要删除的节点的确在链表中。我们需要O(n)的时间才能判断链表中是否包含某一节点。受到O(1)时间的限制，我们不得不把确保点在链表中的责任推给了函数DeleteNode的调用者。

题目二

删除链表中的重复节点

在一个排序的链表中，如何删除重复的节点？例如：在下图（a）中重复的节点被删除之后，链表如图（b）

download.jpg

例如，链表1->2->3->3->4->4->5，处理后为 1->2->5

分析

解决这个问题的第一步是确定删除函数的参数。当然，这个函数需要输入待删除链表的头节点。头节点可能与后面的节点重复，也就是说头节点也可能被删除，因此删除函数应该声明为void DeleteDuplication(ListNode **pHead)，而不是void DeleteDuplication(ListNode *pHead)。

接下来我们从头遍历整个链表，如果当前节点（代码中的pNode）的值与下一个节点的值相同，那么它们就是重复的节点，都应该被删除。

为了保证删除之后链表仍然相连的，我们要把当前节点的前一个节点（代码中的pNode）和后面值比当前节点的值大的节点相连。我们要确保pPreNode始终与下一个没有重复的节点连接在一起

以上图中的链表来分析删除重复节点的过程。

当我们遍历到第一个值为3的节点的时候，pPreNode指向值为2的节点。由于接下来的节点的值还是3，这两个节点应该被删除，因此pPreNode就和第一个值为4的节点相连。接下来由于值为4的两个节点也重复了，还是会被删除，所以pPreNode最终会和值为5的节点相连

代码实现

// 删除重复节点
void DeleteDuplication(ListNode **pHead)
{
    // 头节点为空，直接结束
    if (pHead == nullptr || *pHead == nullptr)
        return;

    ListNode *pPreNode = nullptr; // 记录上一个节点
    ListNode *pNode = *pHead;
    // 顺序遍历
    while (pNode != nullptr) {
        // 获取下一个节点
        ListNode *pNext = pNode->m_pNext;
        // 是否需要删除
        bool needDelete = false;
        // 当前节点值和下一个节点的值是否相等，相等标记该节点需要被删除 
        if (pNext != nullptr && pNext->m_nValue == pNode->m_nValue) {
            needDelete = true;
        }

        if (!needDelete) { // 不删除节点就移动指针
            pPreNode = pNode;
            pNode = pNode->m_pNext;
        }
        else // 当前节点需要删除
        {   
            int value = pNode->m_nValue;
            // 获得要删除的节点
            ListNode *pToBeDel = pNode;

            // 待删除节点不为空，并且值与需要删除的节点相当于，那么就一直循环进行，一直到节点的值不相等
            while (pToBeDel != nullptr && pToBeDel->m_nValue == value) {
                // 将待删除节点的下一个节点赋值给pNext
                pNext = pToBeDel->m_pNext;

                // 删除节点
                delete pToBeDel;
                pToBeDel = nullptr;

                // 重新作为待删除节点
                pToBeDel = pNext;
            }

            // 上一个节点是否存在
            if (pPreNode == nullptr)
                *pHead = pNext;
            else
                pPreNode->m_pNext = pNext;

            // 记录当前节点，继续查找下一个重复节点
            pNode = pNext;
        }
    }
}

参考

《剑指offer》