Java 手寫鏈表完整實作：節點設計、增刪改查、反轉與遞歸操作教學版

鏈表 是基礎資料結構，掌握其手寫實作是面試與教學必備技能。本文提供教學級完整實作，涵蓋節點類設計、單向鏈表核心操作（頭插/尾插/指定位置插入、刪除頭/尾/指定位置、更新、查找、遍歷）、遞歸與迭代反轉、合併有序鏈表、環檢測、尋找中點/倒數第 K 節點等進階操作，程式碼詳註、邊界處理完善、可直接執行驗證。

一、節點類設計

package linkedList;

public class Node<E> {
    E data;           // 資料域（使用泛型避免 Object 強轉）
    Node<E> next;     // 指標域

    public Node(E data, Node<E> next) {
        this.data = data;
        this.next = next;
    }

    public Node(E data) { this(data, null); }

    @Override public String toString() {
        return "Node[" + data + "]";
    }
}

二、單向鏈表核心類 LinkedList<E>

核心欄位

private Node<E> head;  // 頭節點（不存資料的哨兵節點更佳，此處為簡化直接用頭節點）
private int size;      // 節點數量

建構子

public LinkedList() {
    this.head = null;
    this.size = 0;
}

三、核心操作實作

1. 頭插法 addFirst(E e) / addNode(E e)

public void addFirst(E e) {
    head = new Node<>(e, head);
    size++;
}

2. 尾插法 addLast(E e)

public void addLast(E e) {
    if (head == null) { addFirst(e); return; }
    Node<E> cur = head;
    while (cur.next != null) cur = cur.next;
    cur.next = new Node<>(e);
    size++;
}

3. 指定位置插入 insert(int index, E e)

public void insert(int index, E e) {
    if (index < 0 || index > size) throw new IndexOutOfBoundsException("Index: " + index);
    if (index == 0) { addFirst(e); return; }
    Node<E> prev = getNode(index - 1);
    prev.next = new Node<>(e, prev.next);
    size++;
}

private Node<E> getNode(int index) {
    Node<E> cur = head;
    for (int i = 0; i < index; i++) cur = cur.next;
    return cur;
}

4. 刪除頭節點 removeFirst()

public E removeFirst() {
    if (head == null) throw new NoSuchElementException();
    E val = head.data;
    head = head.next;
    size--;
    return val;
}

5. 刪除尾節點 removeLast()

public E removeLast() {
    if (head == null) throw new NoSuchElementException();
    if (head.next == null) return removeFirst();
    Node<E> prev = head;
    while (prev.next.next != null) prev = prev.next;
    E val = prev.next.data;
    prev.next = null;
    size--;
    return val;
}

6. 指定位置刪除 remove(int index)

public E remove(int index) {
    if (index < 0 || index >= size) throw new IndexOutOfBoundsException("Index: " + index);
    if (index == 0) return removeFirst();
    Node<E> prev = getNode(index - 1);
    E val = prev.next.data;
    prev.next = prev.next.next;
    size--;
    return val;
}

7. 更新節點 set(int index, E e)

public void set(int index, E e) {
    getNode(index).data = e;
}

8. 查找節點 get(int index) / indexOf(E e)

public E get(int index) { return getNode(index).data; }

public int indexOf(E e) {
    Node<E> cur = head;
    for (int i = 0; cur != null; i++, cur = cur.next)
        if ((e == null && cur.data == null) || (e != null && e.equals(cur.data)))
            return i;
    return -1;
}

9. 遍歷列印 display()

public void display() {
    Node<E> cur = head;
    while (cur != null) {
        System.out.print(cur.data + " -> ");
        cur = cur.next;
    }
    System.out.println("null");
}

10. 取得長度

public int size() { return size; }

四、進階操作（面試高頻）

1. 迭代反轉 reverse()

public void reverse() {
    Node<E> prev = null;
    Node<E> cur = head;
    while (cur != null) {
        Node<E> next = cur.next;
        cur.next = prev;
        prev = cur;
        cur = next;
    }
    head = prev;
}

2. 遞歸反轉 reverseRecursive()

public void reverseRecursive() {
    head = reverseRecursive(head);
}

private Node<E> reverseRecursive(Node<E> node) {
    if (node == null || node.next == null) return node;
    Node<E> newHead = reverseRecursive(node.next);
    node.next.next = node;
    node.next = null;
    return newHead;
}

3. 合併兩個有序鏈表 mergeSorted(LinkedList<E> other)

public void mergeSorted(LinkedList<E> other) {
    // 假設 E 實作 Comparable
    Node<E> dummy = new Node<>(null);
    Node<E> tail = dummy;
    Node<E> p1 = this.head, p2 = other.head;
    while (p1 != null && p2 != null) {
        if (((Comparable<E>)p1.data).compareTo(p2.data) <= 0) {
            tail.next = p1; p1 = p1.next;
        } else {
            tail.next = p2; p2 = p2.next;
        }
        tail = tail.next;
    }
    tail.next = (p1 != null) ? p1 : p2;
    this.head = dummy.next;
    this.size += other.size;
}

4. 環檢測 hasCycle()（Floyd 快慢指標）

public boolean hasCycle() {
    Node<E> slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) return true;
    }
    return false;
}

5. 尋找中點 findMiddle()

public E findMiddle() {
    Node<E> slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow != null ? slow.data : null;
}

6. 倒數第 K 節點 findKthFromEnd(int k)

public E findKthFromEnd(int k) {
    if (k <= 0) return null;
    Node<E> fast = head, slow = head;
    for (int i = 0; i < k; i++) {
        if (fast == null) return null;
        fast = fast.next;
    }
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }
    return slow != null ? slow.data : null;
}

五、完整可執行測試類

package linkedList;

public class LinkedListDemo {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();

        // 基本操作
        list.addFirst(3);
        list.addFirst(2);
        list.addFirst(1);  // 1->2->3
        list.addLast(4);   // 1->2->3->4
        list.insert(2, 99); // 1->2->99->3->4
        list.display();

        System.out.println("Size: " + list.size());
        System.out.println("Index of 99: " + list.indexOf(99));
        System.out.println("Get(2): " + list.get(2));

        list.set(2, 88);   // 1->2->88->3->4
        list.remove(2);    // 1->2->3->4
        list.removeFirst(); // 2->3->4
        list.removeLast();  // 2->3
        list.display();

        // 進階操作
        LinkedList<Integer> list2 = new LinkedList<>();
        list2.addLast(1); list2.addLast(3); list2.addLast(5);
        LinkedList<Integer> list3 = new LinkedList<>();
        list3.addLast(2); list3.addLast(4); list3.addLast(6);
        list2.mergeSorted(list3);
        System.out.print("Merged: "); list2.display(); // 1->2->3->4->5->6

        list2.reverse();
        System.out.print("Reversed: "); list2.display(); // 6->5->4->3->2->1

        System.out.println("Middle: " + list2.findMiddle());
        System.out.println("2nd from end: " + list2.findKthFromEnd(2));
    }
}

六、哨兵節點優化建議

實務中建議引入虛擬頭節點：

private Node<E> dummy = new Node<>(null); // 永不為 null
// 所有操作統一從 dummy.next 開始，省去 head==null 判斷

優勢：統一邊界邏輯、程式碼更簡潔、避免空指標。

七、總結

手寫鏈表考驗指標操作基本功。核心要點：

1. 節點類封裝資料與 next 指標
2. 頭節點處理（哨兵節點最佳）
3. 插入/刪除核心是修改前驅節點的 next 指標
4. 遍歷時保存 next 避免斷鏈
5. 遞歸操作注意基準情況與棧深度
6. 快慢指標解決中點、倒數 K、環檢測

熟練掌握上述模板，面試手寫鏈表題目將不再是障礙。