剑指Offer-删除链表的结点

1.题目 1

在 时间内删除链表结点。给定单向链表的头指针和一个结点指针，定义一个函数在 时间内删除该结点。

1.1 题目分析

在单链表中删除一个结点，常规做法是从链表的头结点开始，顺序遍历查找要删除的结点，并在链表中删除该结点，但这种方式的时间复杂度为 ，与题目要求不符。

我们可以把要删除结点的下一个结点的内容复制到需要删除的结点上覆盖原有的内容，然后把要删除结点的指针指向要删除结点的下一个结点的下一个结点，再把要删除结点的下一个结点删除，其效果就是把要删除的结点删除了。

1.2 代码实现

// 定义单链表的结点类型
typedef struct ListNode
{
    int data;                                   // 数据域
    struct ListNode* next;                      // 指针域
}ListNode;

void DeleteNode(ListNode** pListHead, ListNode* pDelete)
{
    // 链表的头结点或要删除的结点为 NULL，直接退出
    if (pListHead == NULL || pDelete == NULL) {
        return;
    }
 
    if (pDelete->next != NULL) {                // 要删除的结点不是尾结点
        ListNode* pNext = pDelete->next;
        pDelete->data = pNext->data;            // 将要删除结点的next结点的data复制到要删除结点上
        pDelete->next = pNext->next;            // 将要删除结点的next指向要删除结点的next结点的next

        free(pNext);                            // 释放内存
        pNext = NULL;                           // 将指针置 NULL，防止“野指针”
    } else if (*pListHead == pDelete) {         // 链表只有一个结点，删除头结点（也是尾结点）
        free(pDelete);                         
        pDelete = NULL;                        
        *pListHead = NULL;                      // 将链表头结点置 NULL
    } else {                                    // 链表中有多个结点时，删除尾结点
        ListNode* pNode = *pListHead;

        while (pNode->next != pDelete) {        // 顺序遍历到要删除结点的前序结点
            pNode = pNode->next;
        }

        pNode->next = NULL;                     // 将要删除结点的前序结点的next置 NULL

        free(pDelete);
        pDelete = NULL;
    }
}

2.题目 2

删除链表中重复的结点。

2.1 题目分析

如果当前结点的值与下一个结点的值相同，那么它们就是重复的结点，都需要删除。为了保证删除之后的链表仍然是相连的，要把当前结点的前一个结点和后面值比当前结点值大的结点相连。

2.2 代码实现

// 定义单链表的结点类型
typedef struct ListNode
{
    int data;                                   // 数据域
    struct ListNode* next;                      // 指针域
}ListNode;

void DeleteDuplication(ListNode** pListHead)
{
    // 链表的头结点地址或头结点为 NULL，直接退出
    if (pListHead == NULL || *pListHead == NULL) {
        return;
    }

    ListNode* pPreNode = NULL;                  // 将当前结点的前一个结点置为 NULL
    ListNode* pNode = *pListHead;               // 当前结点指向头结点

    while (pNode != NULL) {                     // 当前结点不为 NULL
        ListNode* pNext = pNode->next;          // 当前结点的next
        bool needDelete = false;                // 是否需要删除，是为true，否为false

        // 若当前结点的next不为 NULL且当前结点的next的data等于当前结点的data，表示有重复的结点，需要删除
        if (pNext != NULL && pNext->data == pNode->data) {
            needDelete = true;
        }

        if (!needDelete) {                      // 若没有重复的结点，则向后遍历
            pPreNode = pNode;
            pNode = pNode->next;
        } else {                                // 若有重复的结点
            int dataValue = pNode->data;        // 当前结点的data赋值给dataValue
            ListNode* pDelete = pNode;          // 令待删除结点指向当前结点

            // 删除重复结点
            while (pDelete != NULL && pDelete->data == dataValue) {
                pNext = pDelete->next;

                free(pDelete);                  // 释放内存
                pDelete = NULL;                 // 将指针置 NULL，防止“野指针”

                pDelete = pNext;
            }

            if (pPreNode == NULL) {             // 从链表的头结点开始就有重复的结点，此时pPreNode为 NULL
                *pListHead = pNext;
            } else {
                pPreNode->next = pNext;
            }

            pNode = pNext;
        }
    }
}

---

个人主页：

www.codeapes.cn