LeetCode 83：從已排序鏈表中移除重複元素

題目描述

給定一個已按遞增順序排列的單鏈表，刪除所有重複的節點，使每個元素只出現一次。

範例：

輸入: 1 -> 1 -> 2
輸出: 1 -> 2

輸入: 1 -> 1 -> 2 -> 3 -> 3
輸出: 1 -> 2 -> 3

解題思路

因為鏈表已排序，重複節點必定相鄰。我們只需遍歷一次，比較當前節點與下一節點的值：

• 若相等，將 current.next 指向 current.next.next（跳過重複節點），不移動 current，繼續比較新的下一節點（因可能連續多個重複）。
• 若不等，將 current 後移一位。

為了最終返回頭節點，需在遍歷前保存原始 head 的引用。

參考代碼 (C++)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (!head || !head->next) return head;
        ListNode* cur = head;
        while (cur->next) {
            if (cur->val == cur->next->val) {
                cur->next = cur->next->next; // 刪除重複節點
            } else {
                cur = cur->next; // 只有不重複時才前進
            }
        }
        return head;
    }
};

複雜度分析

• 時間複雜度：O(n) —— 單次遍歷。
• 空間複雜度：O(1) —— 僅使用常數額外空間。