Java怎么删除排序链表中的重复元素

# Java怎么删除排序链表中的重复元素 在处理链表数据结构时，删除重复元素是一个常见需求。对于已排序的链表，我们可以利用其有序特性高效地完成去重操作。本文将介绍两种Java实现方法：**迭代法**和**递归法**，并分析它们的优缺点。 ## 一、问题描述 给定一个**按升序排列**的链表，删除所有重复元素，使每个元素只出现一次。例如： 输入：1 → 1 → 2 → 3 → 3 输出：1 → 2 → 3 ## 二、迭代法实现 ```java public ListNode deleteDuplicates(ListNode head) { if (head == null || head.next == null) { return head; } ListNode current = head; while (current != null && current.next != null) { if (current.val == current.next.val) { current.next = current.next.next; // 跳过重复节点 } else { current = current.next; // 移动指针 } } return head; } 

时间复杂度：O(n)，只需遍历一次链表
空间复杂度：O(1)，仅使用常量额外空间

三、递归法实现

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; } 

时间复杂度：O(n)
空间复杂度：O(n)（递归栈空间）

四、方法对比

五、边界情况处理

1. 空链表：直接返回null
2. 单节点链表：无需处理
3. 全重复链表：如 1→1→1，应返回1

六、扩展：删除所有重复项

如果需要彻底删除所有重复出现的元素（保留仅出现一次的元素），可采用双指针法：

public ListNode deleteAllDuplicates(ListNode head) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode prev = dummy; while (head != null) { if (head.next != null && head.val == head.next.val) { while (head.next != null && head.val == head.next.val) { head = head.next; } prev.next = head.next; // 跳过所有重复节点 } else { prev = prev.next; } head = head.next; } return dummy.next; } 

七、总结

对于已排序链表的去重： - 优先选择迭代法，兼顾效率和安全性 - 递归法适合链表长度可控的场景 - 注意处理边界条件，保证代码健壮性

掌握这些方法后，可以轻松应对LeetCode 83（保留重复项）和82（删除所有重复项）等相关题目。 “`