無序鏈表去重完整指南：C 與 Java 兩種算法實現（O(n²) vs O(n)）

從無序鏈表中移除重複節點是經典面試題。本文提供 C 與 Java 雙語言實現，對比兩種核心算法：無緩存 O(n²) 雙指針法 與 哈希表 O(n) 空間換時間法，含完整代碼、圖解邏輯、複雜度分析與工程化選型建議。

問題定義

• 輸入：無序單鏈表，可能包含重複值。
• 輸出：原鏈表就地去重，保留首次出現節點，相對順序不變。
• 約束：單鏈表、無序、就地修改。

算法一：無額外空間 O(n²) —— 雙指針嵌套遍歷

核心思想

外層指針 `current` 遍歷每個節點，內層指針 `runner` 檢查 `current` 之後的所有節點，發現重複即刪除。類似選擇排序的去重版。

C 實現

void delete_duplicate1(Node* head) {
    if (head == NULL || head->next == NULL) return;

    Node* current = head->next;           // 假設帶頭節點，首個數據節點
    while (current != NULL) {
        Node* prev = current;
        Node* runner = current->next;     // 內層掃描後續節點

        while (runner != NULL) {
            if (current->data == runner->data) {
                // 刪除 runner
                Node* del = runner;
                prev->next = runner->next;
                runner = prev->next;
                free(del);
            } else {
                prev = runner;
                runner = runner->next;
            }
        }
        current = current->next;
    }
}

Java 實現（遞歸/迭代雙版本）

// 版本一：雙層循環（標準）
public static void deleteDups2(LinkedListNode head) {
    if (head == null) return;

    LinkedListNode current = head;
    while (current != null) {
        LinkedListNode prev = current;
        LinkedListNode runner = current.next;

        while (runner != null) {
            if (current.data == runner.data) {
                prev.next = runner.next;  // 刪除 runner
                runner = prev.next;
            } else {
                prev = runner;
                runner = runner.next;
            }
        }
        current = current.next;
    }
}

// 版本二：遞歸寫法（教學展示）
public static void deleteDupsRecursive(LinkedListNode head) {
    if (head == null) return;
    removeDupsFrom(head, head.next);
    deleteDupsRecursive(head.next);
}

private static void removeDupsFrom(LinkedListNode current, LinkedListNode runner) {
    if (runner == null) return;
    if (current.data == runner.data) {
        // 需傳入 prev 才能刪除，此處略
    }
    removeDupsFrom(current, runner.next);
}

算法二：哈希表 O(n) —— 空間換時間

核心思想

遍歷鏈表，用 `HashSet`/`Hashtable` 記錄已出現值。遇到新值加入集合，遇到重複值刪除。單次遍歷完成。

C 實現（假設理想哈希表）

void delete_duplicate2(Node* head) {
    if (head == NULL || head->next == NULL) return;

    // 假設整數範圍有限，用陣列模擬哈希表
    // 實際項目用 uthash.h 或自定義哈希表
    bool* seen = calloc(MAX_VALUE_RANGE, sizeof(bool));
    if (!seen) return;

    Node* prev = head;
    Node* curr = head->next;
    seen[head->data] = true;  // 頭節點值標記

    while (curr != NULL) {
        if (seen[curr->data]) {
            // 重複：刪除
            Node* del = curr;
            prev->next = curr->next;
            curr = prev->next;
            free(del);
        } else {
            seen[curr->data] = true;
            prev = curr;
            curr = curr->next;
        }
    }
    free(seen);
}

Java 實現（標準庫 HashSet/Hashtable）

public static void deleteDups(LinkedListNode head) {
    if (head == null) return;

    Set seen = new HashSet<>();
    LinkedListNode prev = null;
    LinkedListNode current = head;

    while (current != null) {
        if (seen.contains(current.data)) {
            // 重複：刪除 current
            prev.next = current.next;
            current = current.next;
        } else {
            seen.add(current.data);
            prev = current;
            current = current.next;
        }
    }
}

// 節點定義
class LinkedListNode {
    LinkedListNode next = null;
    int data;
    public LinkedListNode(int d) { data = d; }
}

複雜度對比總結

工程化避坑指南

1. 頭節點處理：帶哨兵頭節點（`head` 不存數據）可統一邏輯，否則需特判頭節點刪除。
2. C 內存管理：`free(del)` 後切勿訪問 `del->next`，先保存 `next` 指針。
3. Java GC：斷開引用即可，無需手動釋放，但注意避免邏輯洩漏（如靜態集合持有節點）。
4. 泛型化：Java 實際用 `LinkedListNode` + `Set`，`T` 需正確實現 `equals/hashCode`。
5. 並發安全：多線程環境下需鎖保護或用 `ConcurrentLinkedQueue` + `ConcurrentHashMap` 重新設計。

完整可運行測試代碼

// Java 測試主類
public class LinkedListDedupeTest {
    public static void main(String[] args) {
        // 構建：1 -> 2 -> 3 -> 2 -> 4 -> 1 -> 5
        LinkedListNode head = new LinkedListNode(1);
        head.appendToTail(2);
        head.appendToTail(3);
        head.appendToTail(2);
        head.appendToTail(4);
        head.appendToTail(1);
        head.appendToTail(5);

        System.out.print("原始: ");
        printList(head);  // 1 2 3 2 4 1 5

        deleteDups(head); // O(n) 哈希法
        System.out.print("去重後: ");
        printList(head);  // 1 2 3 4 5

        // 重構測試 O(n²) 法
        LinkedListNode head2 = buildList(1,2,3,2,4,1,5);
        deleteDups2(head2);
        System.out.print("O(n²)去重: ");
        printList(head2); // 1 2 3 4 5
    }

    static LinkedListNode buildList(int... vals) {
        if (vals.length == 0) return null;
        LinkedListNode head = new LinkedListNode(vals[0]);
        for (int i = 1; i < vals.length; i++) head.appendToTail(vals[i]);
        return head;
    }

    static void printList(LinkedListNode head) {
        while (head != null) {
            System.out.print(head.data + " ");
            head = head.next;
        }
        System.out.println();
    }
}

面試追問預案

1. 若鏈表已排序？：單指針 O(n) 相鄰比較即可，無需哈希表。
2. 若不能修改原鏈表？：構建新鏈表，複制非重複節點，O(n) 時間 O(n) 空間。
3. 哈希衝突怎麼辦？：Java `HashSet` 自動處理（鏈表/紅黑樹），C 需自行實現開放定址/拉鏈法。
4. 如何驗證去重正確性？：遍歷結果鏈表插入 `HashSet`，若 `add` 返回 `false` 則有殘留重複。

掌握無序鏈表去重的兩種經典算法，理解時空權衡本質，是數據結構面試與工程實踐的雙重保障。生產環境首選哈希表法，特殊約束下再退化至雙指針法。