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（删除所有重复项）等相关题目。 “`