您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 相關知識

Java 手寫有序鏈表實現插入排序與單鏈表就地反轉完整教學

編輯：Java 相關知識

有序鏈表核心特性

有序鏈表 維持節點按關鍵字（自然順序或 Comparator）排序。核心操作複雜度：

插入：需遍歷查找位置 O(N)，但無需移動數據元素，只調整指標
刪除最小/最大值：頭/尾節點直接刪除 O(1)
查找/刪除指定值：O(N)

適用場景：優先權佇列、頻繁存取極值、線上排序、記憶體受限環境（避免陣列擴容複製）。

完整泛型實現


public class SortedLinkedList<T extends Comparable<T>> {
    private Node<T> first;
    static class Node<T> { T data; Node<T> next; Node(T d){data=d;} }
    
    public void insert(T data) {
        Node<T> newNode = new Node<>(data);
        Node<T> curr = first, prev = null;
        // 找到第一個大於 data 的節點位置
        while (curr != null && data.compareTo(curr.data) > 0) {
            prev = curr; curr = curr.next;
        }
        if (prev == null) { first = newNode; } // 插入頭部
        else { prev.next = newNode; }
        newNode.next = curr;
    }
    
    public T removeFirst() { // 刪除並返回最小值
        if (first == null) return null;
        T val = first.data;
        first = first.next;
        return val;
    }
    
    // 鏈表插入排序：將無序陣列元素逐個插入有序鏈表
    public void sortArray(T[] array) {
        for (T item : array) insert(item);
        // 回寫陣列
        int i = 0;
        for (Node<T> n = first; n != null; n = n.next) array[i++] = n.data;
    }
    
    public void display() { for (Node<T> n=first; n!=null; n=n.next) System.out.print(n.data+" "); }
}

測試驗證


public static void main(String[] args) {
    SortedLinkedList<Integer> list = new SortedLinkedList<>();
    Integer[] arr = {595, 725, 310, 702, 444};
    System.out.println("排序前：" + Arrays.toString(arr));
    list.sortArray(arr);
    System.out.print("鏈表排序後："); list.display(); // 310 444 595 702 725
}

單鏈表就地反轉：三種經典寫法

方法一：三指針迭代法（最推薦，O(1) 空間）


public static Node reverseIterative(Node head) {
    Node prev = null, curr = head, next;
    while (curr != null) {
        next = curr.next;  // 暫存後繼
        curr.next = prev;  // 反轉指標
        prev = curr;       // 前移 prev
        curr = next;       // 前移 curr
    }
    return prev; // 新頭節點
}

方法二：遞迴法（簡潔但 O(N) 棧空間）


public static Node reverseRecursive(Node head) {
    if (head == null || head.next == null) return head;
    Node newHead = reverseRecursive(head.next);
    head.next.next = head; // 核心：下一節點指回當前
    head.next = null;      // 斷開原向後指標
    return newHead;
}

方法三：頭插法構建新鏈表（易理解，需額外空間或就地操作）


public static Node reverseHeadInsert(Node head) {
    Node newHead = null;
    while (head != null) {
        Node next = head.next;
        head.next = newHead;
        newHead = head;
        head = next;
    }
    return newHead;
}

反轉過程圖解（以 1→2→3→4 為例）

初始: 1 → 2 → 3 → 4 → null
      
迭代步驟:
prev=null, curr=1: next=2, 1→null, prev=1, curr=2
prev=1,    curr=2: next=3, 2→1,   prev=2, curr=3
prev=2,    curr=3: next=4, 3→2,   prev=3, curr=4
prev=3,    curr=4: next=null,4→3, prev=4, curr=null
結束: 返回 prev=4, 鏈表: 4 → 3 → 2 → 1 → null

複雜度對比總結

操作	有序鏈表	無序陣列	堆排序/快排
插入單元素	O(N)	O(1) 尾部	O(log N)
批量構建排序	O(N²)	O(N log N)	O(N log N)
取最小值	O(1)	O(N)	O(1)
空間複雜度	O(N) 節點	O(1) 原地	O(1)~O(log N)