AC202-删除单链表中重复的结点，仅保留第一个¶

代码实现¶

C
// 函数 del：删除单链表中重复的结点，仅保留第一个出现的结点
void del(LinkList L) {
    LinkList p = L->next; // 初始化指针 p，指向链表的第一个结点

    // 外层循环：遍历链表中的每个结点
    while (p != NULL) { 
        LinkList r = p; // 初始化指针 r，从当前结点 p 开始检查后续结点

        // 内层循环：查找并删除与当前结点 p 数据相同的后续结点
        while (r->next != NULL) {
            if (r->next->data == p->data) { // 如果找到重复结点
                LinkList q = r->next;      // 暂存需要删除的结点 q
                r->next = q->next;         // 跳过结点 q，将其从链表中移除
                free(q);                   // 释放结点 q 的内存
            } else {
                r = r->next;               // 如果没有找到重复结点，继续向后移动 r
            }
        }

        p = p->next; // 处理完当前结点 p 后，移动到下一个结点
    }
}

代码逻辑解析¶

初始化指针：
p 指针用于遍历链表中的每个结点。
r 指针用于从当前结点 p 开始，检查后续结点是否有重复值。
外层循环：
外层循环依次遍历链表中的每个结点 p。
对于每个结点 p，内层循环负责查找并删除其后续结点中值与 p->data 相同的结点。
内层循环：
内层循环通过 r 指针从当前结点 p 开始，逐个检查后续结点。
如果发现 r->next->data == p->data，说明找到了一个重复结点，执行删除操作：
- 使用临时指针 q 指向需要删除的结点。
- 修改 r->next，跳过结点 q。
- 释放结点 q 的内存。
指针移动：
如果未找到重复结点，则将 r 指针向后移动一位。
外层循环中，处理完当前结点 p 后，将其移动到下一个结点。

时间复杂度分析¶

外层循环：
外层循环遍历链表中的每个结点，最多执行 n 次（n 是链表的长度）。
内层循环：
对于每个结点 p，内层循环需要检查其后续的所有结点。
在最坏情况下（链表中所有结点的值都相同），内层循环需要遍历剩余的所有结点。
总的时间复杂度：
外层循环执行 n 次，内层循环在最坏情况下需要执行 (n-1) + (n-2) + ... + 1 次。
这是一个等差数列求和问题，时间复杂度为 O(n²)。

空间复杂度分析¶

该算法只使用了常量级别的额外空间（如指针 p, r, q），没有使用与输入规模相关的额外空间。
因此，空间复杂度为 O(1)。

较难理解部分的说明¶

为什么需要两个嵌套循环？¶

外层循环负责遍历链表中的每个结点 p。
内层循环负责从 p 开始，检查后续结点是否有重复值。
通过两层循环，可以确保每个结点的值都被检查，并删除所有重复结点。

删除操作的细节¶

删除操作的关键是修改链表的指针关系。假设链表如下：
Text Only
1
A -> B -> C -> D
如果要删除结点 C，则需要将 B->next 指向 D，然后释放 C 的内存。

图解说明¶

假设链表如下：

Text Only
1	`L -> 1 -> 2 -> 3 -> 2 -> 4 -> 3`

初始状态：

Text Only
1 2	`p -> 1 r -> 1`

第一次外层循环：p 指向 1，内层循环未发现重复结点，p 移动到 2。
第二次外层循环：p 指向 2，内层循环发现后续结点中有一个重复的 2，删除它。
Text Only
1
L -> 1 -> 2 -> 3 -> 4 -> 3
第三次外层循环：p 指向 3，内层循环发现后续结点中有一个重复的 3，删除它。
Text Only
1
L -> 1 -> 2 -> 3 -> 4

最终结果：

Text Only
1	`L -> 1 -> 2 -> 3 -> 4`

延伸知识点¶

优化方法：
当前算法的时间复杂度为 O(n²)，可以通过引入哈希表（HashSet）优化到 O(n)。
使用哈希表记录已经访问过的值，在遍历链表时直接判断是否重复。
链表的基本操作：
链表的插入、删除、遍历是链表操作的核心内容，熟练掌握这些操作有助于解决更复杂的链表问题。
扩展问题：
如果需要删除所有重复结点（包括第一个出现的结点），如何修改算法？
如果链表是双向链表，如何设计删除重复结点的算法？