CS-Notes 剑指 Offer：删除链表中重复的结点——递归与迭代两种完整解法

本篇基于 CS-Notes 仓库中《18.2 删除链表中重复的结点》一文展开，完整继承原文档的题目描述与递归解法，并结合仓库中链表题解（Leetcode 题解 - 链表、18.1 在 O(1) 时间内删除链表节点%20时间内删除链表节点.md)）中的相关技法进行纵深扩充。读完后你能掌握：该题与"去重保留一份"题型的本质区别、原文档递归解法的逐步推演过程、等价的迭代（哨兵节点）实现、以及时间/空间复杂度与边界条件的完整分析。

题目描述

原始文档给出的题目是：

在一个排序的链表中，存在重复的结点。请删除该链表中的重复结点，重复的结点不保留（即全部删除）。

示例如下：

注意题目前提是链表已排序，因此所有重复值必然相邻出现，这保证了只需局部比较相邻结点即可判断重复，不需要全局统计频次。

这里有一个极易混淆的关键点：本题要求把重复值全部删除（2->2 整组消失、3->3 整组消失），而不是只保留一份。仓库中 Leetcode 题解 - 链表 收录的"4. 从有序链表中删除重复节点"（Leetcode 83 Remove Duplicates from Sorted List）是另一类题型——它保留一份：

// 仅保留一份：1->1->2 -> 1->2
public ListNode deleteDuplicates(ListNode head) {
    if (head == null || head.next == null) return head;
    head.next = deleteDuplicates(head.next);
    return head.val == head.next.val ? head.next : head;
}

两者的判断逻辑几乎一致，唯一区别在于发现重复时"跳过整组"还是"跳过重复部分"。面试中先确认清楚这一语义，再动手写代码。

原文档解法：递归

原始文档给出的完整代码如下：

public ListNode deleteDuplication(ListNode pHead) {
    if (pHead == null || pHead.next == null)
        return pHead;
    ListNode next = pHead.next;
    if (pHead.val == next.val) {
        while (next != null && pHead.val == next.val)
            next = next.next;
        return deleteDuplication(next);
    } else {
        pHead.next = deleteDuplication(pHead.next);
        return pHead;
    }
}

逐行拆解其执行逻辑：

1. 递归出口：pHead == null（已经删到链表外）或 pHead.next == null（只剩一个结点，不可能重复），直接返回当前头结点。
2. 头结点参与重复：先取 next = pHead.next，若 pHead.val == next.val，说明头结点所在的重复组至少有两个。此时用 while 循环让 next 一路向右跳过整组同值结点，然后直接递归处理 next 开始的剩余链表，并让递归结果成为新的头结点——这一步天然完成了"整组摘除"。
3. 头结点不重复：pHead 必须保留，于是对 pHead.next 递归，把去重后的子链表接回 pHead.next，返回 pHead。

以示例 1->2->2->3->3->4 推演调用链：

• deleteDuplication(1)：1 不重复，递归处理 2->2->3->3->4；
• deleteDuplication(2)：2 重复，while 跳到 3->3->4，递归处理；
• deleteDuplication(3)：3 重复，while 跳到 4，递归处理；
• deleteDuplication(4)：next == null，命中出口返回 4；
• 逐层回卷后结果为 1->4，与上图一致。

由于"是否重复"只依赖相邻两结点，且每个结点最多被访问常数次，时间复杂度为 O(n)；递归调用深度最大为 n，空间复杂度为 O(n)（递归栈开销）。

等价解法：迭代 + 哨兵节点

原文档的递归版本在"头结点也可能被整组删除"的场景下处理得很干净，但面试手写时迭代写法通常更不易出错。核心技巧是引入一个哨兵节点（dummy），让"头结点被删除"也统一为"中间结点被删除"的问题：

public ListNode deleteDuplication(ListNode pHead) {
    // 哨兵节点，把 head 也变成普通后继
    ListNode dummy = new ListNode(0);
    dummy.next = pHead;
    ListNode cur = dummy;
    while (cur.next != null && cur.next.next != null) {
        if (cur.next.val == cur.next.next.val) {
            int val = cur.next.val;
            // 跳过所有值为 val 的结点
            while (cur.next != null && cur.next.val == val) {
                cur.next = cur.next.next;
            }
        } else {
            cur = cur.next;
        }
    }
    return dummy.next;
}

要点：

• cur 始终停在"待判断结点的前驱"上，重复时不移动 cur（因为 cur.next 已经被整组摘除，需要重新判断新的后继），不重复时才 cur = cur.next 前进；
• 返回值是 dummy.next 而非 dummy，dummy 只用于统一处理边界；
• 复杂度：时间 O(n)、空间 O(1)。

两种解法可对照记忆：递归版的"跳过整组"对应迭代版的内层 while，递归版的"返回新头"对应迭代版的哨兵机制。

与仓库内相关题型的技法关联

结合仓库中剑指 Offer 链表章节（见剑指 Offer 题解 - 目录），本题的"摘除结点"操作与几道经典题共享底层技法，可以对照复习：

• 18.1 在 O(1) 时间内删除链表节点%20时间内删除链表节点.md)：该题利用"把后继结点的值复制过来再删后继"来绕过前驱指针，平均时间复杂度 O(1)。两者对比可以看出：当没有前驱引用时（18.1 只给 tobeDelete 本身），与只有前驱引用时（18.2 从头部顺序扫描），操作策略完全不同。18.2 的迭代解法正是靠 cur 持有前驱引用，才能安全地把整组结点的后继指针改写到 cur.next 上。
• 24. 反转链表、25. 合并两个排序的链表：同样反复使用"双指针维护前后关系 + 逐结点改指针"的模式，与本题内层 while 的指针改写是同一种基本功。
• 6. 从尾到头打印链表：与原文档递归版同属"用递归栈模拟从尾到头"的思路，可以体会递归处理链表时的通用节奏：先信任"子链表已处理好"，再处理当前结点与子链表的拼接。

边界条件与复杂度小结

输入情况	结果	说明
null	null	递归出口第一分支直接处理
单结点 1	1	pHead.next == null，不重复
全部重复 2->2	null	整组被 while 跳过，next 为 null，递归返回 null
无重复 1->2->3	原链表	每次走 else 分支，等价于原样返回
头结点参与重复 1->1->2	2	递归版返回 deleteDuplication(next)，迭代版靠 dummy 兜底

复杂度结论：两种解法时间均为 O(n)（每个结点至多被跳过一次），空间上递归版 O(n)（栈深）、迭代版 O(1)。若题目规模可能使递归栈溢出（链表极长），应优先选择迭代 + 哨兵节点版本。

小结

本题（对应 原始文档）的核心考点有三个：

1. 准确识别"重复值全部删除"的语义，区分于 Leetcode 83 的"保留一份"；
2. 掌握递归解法中"跳过整组同值结点后让递归结果作新头"的写法；
3. 能独立写出带哨兵节点的迭代解法，并正确区分 cur 何时前进、何时原地重查。

仓库中该文档位于剑指 Offer 链表章节，可与 18.1 在 O(1) 时间内删除链表节点%20时间内删除链表节点.md) 以及 Leetcode 题解 - 链表 中的第 4、5 题（有序去重、删除倒数第 n 个节点）一并练习，形成对"链表结点摘除"这一类操作的完整理解。