AC201-删除递增链表中重复的结点，仅保留第一个

代码实现

// 函数 del：删除递增链表中重复的结点，仅保留第一个
void del(LinkList L) {
    // 从链表的第一个有效结点开始遍历
    LNode* p = L->next;

    // 循环条件：当前结点的下一个结点不为空
    while (p->next != NULL) {
        LinkList q = p->next; // q 指向当前结点的下一个结点

        // 如果当前结点和下一个结点的数据域相等，则删除下一个结点
        if (p->data == q->data) {
            p->next = q->next; // 将当前结点的 next 指针指向 q 的下一个结点
            free(q);           // 释放 q 结点占用的内存空间
        } else {
            // 如果数据不相等，则移动 p 指针到下一个结点
            p = p->next;
        }
    }
}

---

代码逻辑解析

1. 初始化指针：
2. p 指针从链表的第一个有效结点（头结点的下一个结点）开始遍历。

3. 这样设计是因为头结点通常不存储有效数据，仅作为链表操作的辅助结点。

4. 循环条件：

5. 当 p->next != NULL 时继续循环，即当前结点的下一个结点存在。

6. 这样可以确保在访问 q = p->next 时不会出现空指针异常。

7. 重复检测：

8. q 指针指向 p 的下一个结点。

9. 比较 p->data 和 q->data 的值：

   • 如果相等，说明找到了重复结点，需要删除 q 结点。
   • 如果不相等，说明没有重复，移动 p 指针继续遍历。

10. 删除操作：

11. 当发现重复结点时，将 p->next 指向 q->next，跳过 q 结点。

12. 使用 free(q) 释放被删除结点的内存空间，避免内存泄漏。

13. 指针移动：

14. 只有在没有删除结点时才移动 p 指针，这样可以连续处理多个重复结点。

---

时间复杂度分析

• 遍历次数：
• 每个结点最多被访问一次，总共访问 n-1 个结点（不包括头结点）。

• 每次循环都执行常数时间的操作（比较、指针操作、可能的删除操作）。

• 删除操作：

• 每个重复结点只被删除一次，删除操作的时间复杂度为 O(1)。

综上，算法的时间复杂度为 O(n)，其中 n 是链表中结点的总数。

---

空间复杂度分析

• 该算法只使用了常量级别的额外空间（如指针变量 p 和 q）。
• 没有使用与链表长度相关的额外存储空间。
• 删除操作释放了重复结点的内存，不会增加空间使用量。

因此，空间复杂度为 O(1)。

---

较难理解部分的说明

为什么删除结点后不移动 p 指针？

这是算法的关键设计：

• 当删除 q 结点后，p->next 直接指向了 q 的下一个结点。
• 如果立即移动 p 指针，可能会跳过对新 p->next 结点的检查。
• 不移动 p 指针可以确保连续的重复结点都能被正确检测和删除。

图解说明

假设链表如下（递增序列）：

头结点 -> 1 -> 2 -> 2 -> 3 -> 3 -> 3 -> 4 -> NULL

执行过程： 1. 第一次循环：p指向第一个2，q指向第二个2 - 发现重复，删除q结点 - 链表变为：1 -> 2 -> 3 -> 3 -> 3 -> 4 -> NULL - p仍指向第一个2

1. 第二次循环：p指向第一个2，q指向3

2. 不重复，p移动到3

3. 第三次循环：p指向第一个3，q指向第二个3

4. 发现重复，删除q结点
5. 继续处理直到所有重复都被删除

最终结果：

头结点 -> 1 -> 2 -> 3 -> 4 -> NULL

---

延伸知识点

1. 链表操作的安全性

// 更安全的实现版本
void del_safe(LinkList L) {
    if (L == NULL || L->next == NULL) {
        return; // 处理空链表或只有头结点的情况
    }

    LinkList p = L->next;
    while (p != NULL && p->next != NULL) {
        LinkList q = p->next;
        if (p->data == q->data) {
            p->next = q->next;
            free(q);
            // 注意：这里不移动p指针
        } else {
            p = p->next;
        }
    }
}

2. 相关链表操作算法

• 删除所有重复结点（包括第一个）：需要使用前驱指针
• 删除指定值的所有结点：类似思路，但比较条件不同
• 链表去重的其他策略：使用哈希表记录已出现元素（时间O(n)，空间O(n)）

3. 递归实现思路

// 递归方式删除重复结点
void del_recursive(LinkList head) {
    if (head == NULL || head->next == NULL) {
        return;
    }

    if (head->data == head->next->data) {
        LinkList temp = head->next;
        head->next = head->next->next;
        free(temp);
        del_recursive(head); // 继续检查当前结点
    } else {
        del_recursive(head->next);
    }
}

4. 扩展应用场景

• 有序数组去重：类似双指针法
• 多个有序链表合并去重：需要更复杂的比较逻辑
• 带重复计数的去重：记录每个元素的出现次数