您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 程式設計入門

無序鏈表去重算法：C 語言與 Java 兩種實現對比

編輯：Java 程式設計入門

問題定義

在不使用額外緩存（或允許使用）前提下，移除無序單鏈表中的重複節點。

方案一：無額外空間 O(n²) 雙指針法

外層指針 pPos 遍歷每個節點，內層指針 q 掃描後續節點，發現重複則刪除。

C 實現

void delete_duplicate1(node* head) {
    node* pPos = head->next;
    while (pPos) {
        node *p = pPos, *q = pPos->next;
        while (q) {
            if (pPos->data == q->data) {
                node* del = q;
                p->next = q->next;
                q = p->next;
                free(del);
            } else { p = q; q = q->next; }
        }
        pPos = pPos->next;
    }
}

方案二：哈希表 O(n) 空間換時間

遍歷鏈表，哈希集合記錄已見值，遇到重複即刪除。

C 實現（假設完美哈希）

void delete_duplicate2(node* head) {
    node *p = head->next, *q = p->next;
    memset(hash, 0, sizeof(hash));
    hash[p->data] = 1;
    while (q) {
        if (hash[q->data]) { /* 刪除 q */ }
        else { hash[q->data] = 1; p = q; q = q->next; }
    }
}

Java 實現

public static void deleteDups(LinkedListNode n) {
    Set set = new HashSet<>();
    LinkedListNode prev = null;
    while (n != null) {
        if (set.contains(n.data)) prev.next = n.next;
        else { set.add(n.data); prev = n; }
        n = n.next;
    }
}

// 無緩存版 O(n²)
public static void deleteDups2(LinkedListNode head) {
    if (head == null) return;
    LinkedListNode prev = head, curr = head.next;
    while (curr != null) {
        LinkedListNode runner = head;
        while (runner != curr) {
            if (runner.data == curr.data) {
                prev.next = curr.next;
                curr = prev.next;
                break;
            }
            runner = runner.next;
        }
        if (runner == curr) { prev = curr; curr = curr.next; }
    }
}