1. 问题分析与解法思路
链表去重是算法学习中的经典问题，LeetCode第83题"删除排序链表中的重复元素"要求我们保留每个元素的一次出现，删除所有后续重复项。面对这个问题，我们需要深入理解链表的特性和操作方式。
链表与数组最大的区别在于其非连续存储的特性。每个节点包含值和指向下一个节点的指针，这种结构使得插入和删除操作的时间复杂度可以降到O(1)，但同时也失去了随机访问的能力。在本题中，链表已经排序，这为我们提供了重要线索——重复元素必定相邻。
1.1 双指针法的选择依据
为什么选择双指针法来解决这个问题？主要有三个原因：
- 有序性保证：由于链表已排序，重复元素必然相邻，只需比较相邻节点即可
- 空间效率：题目要求原地修改，双指针法只需常数额外空间
- 时间效率：单次遍历即可完成，时间复杂度为O(n)
在实际编码中，我们可以将当前节点和它的next指针视为两个指针，这种设计巧妙地减少了指针变量的数量。
2. 代码实现与细节解析
让我们仔细分析给出的解决方案代码，理解每个关键点的设计意图：
class Solution { public ListNode deleteDuplicates(ListNode head) { ListNode pre = head; while(pre != null && pre.next != null){ if(pre.val == pre.next.val){ pre.next = pre.next.next; }else{ pre = pre.next; } } return head; } }2.1 边界条件处理
循环条件pre != null && pre.next != null确保了我们在处理链表时不会出现空指针异常。这个条件考虑了两种边界情况：
- 空链表（head为null）
- 链表只有一个节点（pre.next为null）
2.2 核心逻辑分解
代码的核心逻辑可以分为两部分：
- 发现重复：当
pre.val == pre.next.val时，通过pre.next = pre.next.next跳过重复节点 - 移动指针：当相邻节点值不同时，才将pre指针移动到下一个节点
这种设计确保了我们会连续检查所有可能的重复项，直到遇到不同值为止。
3. 时间复杂度与空间复杂度分析
3.1 时间复杂度
该算法只对链表进行一次遍历，每个节点最多被访问两次（一次作为当前节点，一次作为前一个节点的next），因此时间复杂度为O(n)。
3.2 空间复杂度
算法只使用了常数级别的额外空间（pre指针），因此空间复杂度为O(1)。
4. 常见问题与调试技巧
4.1 空链表处理
初学者常犯的错误是忘记处理空链表的情况。我们的循环条件已经包含了这种检查，但为了代码更健壮，可以在函数开始时显式检查：
if(head == null) return null;4.2 指针移动逻辑
另一个常见困惑是为什么只在值不等时才移动pre指针。这是因为可能有多个连续重复值，我们需要确保检查完所有可能的重复项后才能移动指针。
4.3 调试建议
在调试链表问题时，可以：
- 绘制链表示意图，标注指针位置
- 使用小规模测试用例（如[1,1,1]）
- 在关键节点打印当前链表状态
5. 算法优化与变种
5.1 递归解法
这个问题也可以用递归解决，虽然空间复杂度会变为O(n)：
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; }递归解法更简洁，但可能更难理解，且不适合处理超长链表（可能导致栈溢出）。
5.2 未排序链表去重
如果链表未排序，我们可以使用哈希表来记录已出现过的值：
public ListNode deleteDuplicates(ListNode head) { Set<Integer> seen = new HashSet<>(); ListNode prev = null, curr = head; while(curr != null){ if(seen.contains(curr.val)){ prev.next = curr.next; }else{ seen.add(curr.val); prev = curr; } curr = curr.next; } return head; }这种方法的时间复杂度仍为O(n)，但空间复杂度变为O(n)。
6. 实际应用场景
链表去重算法在实际开发中有多种应用：
- 数据库查询结果处理：去除重复记录
- 日志分析：合并相同类型的日志条目
- 缓存系统：避免存储重复数据
- 网络数据包处理：过滤重复数据包
理解这类基础算法问题有助于我们在面对更复杂的实际问题时，能够快速识别问题本质并选择适当的解决方案。
7. 扩展练习建议
为了巩固对链表操作的理解，建议尝试以下LeetCode题目：
- 删除排序链表中的重复元素 II（保留不重复元素）
- 环形链表（判断链表是否有环）
- 反转链表
- 合并两个有序链表
- 删除链表的倒数第N个节点
每解决一个问题后，尝试分析最优解的时间和空间复杂度，并思考可能的优化方向。
