概述#

Linked List 是一種由節點（node）序列組成的資料結構：

• Singly Linked List（單向鏈結串列）：每個節點指向下一個節點
• Doubly Linked List（雙向鏈結串列）：每個節點同時擁有指向下一個節點與前一個節點的指標

雙向鏈結串列示意圖：
[ 1 ] <-> [ 5 ] <-> [ 2 ] <-> [ 13 ] <-> [ 7 ] <-> [ 3 ]

與陣列不同，linked list 無法以常數時間存取特定索引的元素——若要找第 K 個元素，必須從頭遍歷 K 個節點。

Linked list 的優勢在於可以在開頭以常數時間新增或刪除元素，這對特定應用場景非常實用。

在面試中討論 linked list 時，必須先釐清題目是單向還是雙向鏈結串列。

Creating a Linked List#

以下是一個基本的單向 linked list 實作：

class Node {
    Node next = null;
    int data;

    public Node(int d) {
        data = d;
    }

    void appendToTail(int d) {
        Node end = new Node(d);
        Node n = this;
        while (n.next != null) {
            n = n.next;
        }
        n.next = end;
    }
}

在這個實作中，我們透過 head Node 的引用來存取 linked list，而不是一個獨立的 LinkedList 物件。這樣的缺點是：若多個物件持有這個 linked list 的引用，當 head 改變時，某些物件可能仍指向舊的 head。

可以考慮另外建立一個 LinkedList 類別來包裝 Node，其唯一的成員變數就是 head Node，這樣就能解決上述問題。

Deleting a Node from a Singly Linked List#

從 linked list 刪除節點的邏輯很直觀：找到節點 n 的前一個節點 prev，將 prev.next 設為 n.next。

若是雙向鏈結串列，還需要更新 n.next.prev = n.prev。

兩個關鍵注意事項：

1. 檢查 null pointer
2. 必要時更新 head 或 tail 指標

Node deleteNode(Node head, int d) {
    Node n = head;

    if (n.data == d) {
        return head.next; /* moved head */
    }

    while (n.next != null) {
        if (n.next.data == d) {
            n.next = n.next.next;
            return head; /* head didn't change */
        }
        n = n.next;
    }
    return head;
}

若使用 C 或 C++ 等需要手動管理記憶體的語言，應考慮是否需要釋放被刪除節點的記憶體。

The “Runner” Technique#

Runner 技巧（又稱第二指標技巧）是許多 linked list 題目的核心思路。

做法是同時用兩個指標遍歷 linked list，其中一個跑得比另一個快：

• fast pointer：可能比 slow pointer 超前固定距離，或是每次跳過多個節點
• slow pointer：以正常速度遍歷

應用範例：

假設有一個 linked list：a₁ -> a₂ -> ... -> aₙ -> b₁ -> b₂ -> ... -> bₙ，想將其重新排列為 a₁ -> b₁ -> a₂ -> b₂ -> ... -> aₙ -> bₙ（已知長度為偶數）。

做法：讓 p1 每移動兩步，p2 移動一步。當 p1 到達尾端時，p2 恰好在中點。再將 p1 移回頭部，開始「交織」兩段元素——p2 每選一個元素，就插入到 p1 之後。

Recursive Problems#

許多 linked list 問題都依賴遞迴（recursion）。如果在解題時遇到困難，可以思考遞迴解法是否可行。

遞迴演算法的空間複雜度至少為 O(n)，n 為遞迴呼叫的深度。所有遞迴演算法理論上都可以用迴圈實作，但迴圈版本可能複雜得多。

面試題目列表#