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)（遞歸?？臻g）

四、方法對比

五、邊界情況處理

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（刪除所有重復項）等相關題目。 “`