1. 问题分析与解题思路链表去重是数据结构基础操作中的经典问题尤其当链表已经排序时我们可以利用有序性实现高效处理。这道题在面试中出现频率极高考察的是对链表操作的熟练程度和边界条件的处理能力。1.1 题目重述给定一个已排序的链表删除所有重复的元素使每个元素只出现一次。例如输入1-1-2输出1-2输入1-1-2-3-3输出1-2-31.2 核心难点解析虽然题目看似简单但实际处理时有几个关键点需要注意头节点可能被删除的情况连续多个重复节点的处理链表末尾的边界条件空链表的特殊情况新手常见误区直接修改节点值而非操作指针这在实际工程中可能引发内存问题。2. 双指针解法详解2.1 算法思路采用快慢双指针策略慢指针slow指向当前已处理好的链表尾部快指针fast探索后续节点当fast发现新值时将slow.next指向fast完成去重操作。时间复杂度O(n)空间复杂度O(1)。2.2 Python实现代码class ListNode: def __init__(self, val0, nextNone): self.val val self.next next def deleteDuplicates(head: ListNode) - ListNode: if not head: return None slow head fast head.next while fast: if slow.val ! fast.val: slow.next fast slow slow.next fast fast.next slow.next None # 截断后续可能存在的重复节点 return head2.3 关键操作解析初始化时slow指向头节点fast指向第二个节点当fast.val ≠ slow.val时将slow.next指向fastslow移动到fast位置无论是否相等fast都继续前进循环结束后必须执行slow.next None实测技巧在纸上画出链表变化过程能帮助理解指针移动逻辑。3. 递归解法与比较3.1 递归思路递归解法更简洁但空间复杂度为O(n)def deleteDuplicates(head): if not head or not head.next: return head head.next deleteDuplicates(head.next) return head if head.val ! head.next.val else head.next3.2 方法对比特性迭代法递归法时间复杂度O(n)O(n)空间复杂度O(1)O(n)代码简洁度中等高适用场景长链表短链表/教学4. 边界条件与测试用例4.1 必须考虑的测试场景空链表输入None预期输出None单节点链表输入1-None预期不变全重复链表1-1-1-None输出1-None无重复链表1-2-3-None预期不变交替重复1-1-2-3-3-None4.2 调试技巧在实现时建议添加打印函数def print_list(head): while head: print(head.val, end-) head head.next print(None)5. 工程实践中的优化5.1 内存安全处理实际工程中应该显式释放被删除节点的内存Python有GC可不处理# 在迭代法中补充 while fast: if slow.val ! fast.val: slow.next fast slow slow.next else: temp fast # 保存待释放节点 fast fast.next del temp # 释放内存5.2 多语言实现要点C需要注意指针操作和内存释放Java需处理对象引用Go需要注意指针接收者的使用6. 算法扩展思考6.1 相关问题变种未排序链表去重需使用哈希表删除所有重复元素保留唯一出现反向链表去重6.2 实际应用场景数据库结果集去重日志流水线处理消息队列的幂等处理链表操作是许多底层系统的基础比如Redis的列表实现操作系统进程调度队列文件系统的块链式存储7. 刷题策略建议先写测试用例再实现画图辅助理解指针变化比较不同解法的优劣记录每种解法的时间/空间复杂度定期复习经典题目对于准备面试的同学建议将这道题与以下题目结合练习反转链表LeetCode 206环形链表检测LeetCode 141合并两个有序链表LeetCode 21最后分享一个调试技巧在链表问题中可以在节点类中添加__repr__方法方便打印def __repr__(self): return fListNode({self.val})
