您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 綜合教學

LeetCode 148：鏈表排序 - 歸併排序 O(n log n) 實現

編輯：Java 綜合教學

LeetCode 148：鏈表排序 - 歸併排序 O(n log n) 實現

題目要求：在 O(n log n) 時間、O(1) 空間複雜度下對單鏈表排序。本文對比數組轉換法(不滿足空間要求)與標準歸併排序法，給出完整遞歸與迭代實現。

題目分析

單鏈表無法隨機訪問，快排不適用
歸併排序天然適配鏈表：分割只需快慢指針，合併只需指針操作
遞歸版空間 O(log n) (棧)，迭代版可達 O(1)

錯誤示範：數組轉換法 (空間 O(n))

// 此法不符合 O(1) 空間要求，僅供參考
public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode p = head; int count = 0;
    while (p != null) { count++; p = p.next; }
    int[] arr = new int[count];
    p = head;
    for (int i = 0; i < count; i++) { arr[i] = p.val; p = p.next; }
    Arrays.sort(arr);
    p = head;
    for (int val : arr) { p.val = val; p = p.next; }
    return head;
}

標準解法：自頂向下歸併排序 (O(log n) 空間)

public class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) return head;
        return mergeSort(head);
    }
    
    private ListNode mergeSort(ListNode head) {
        if (head.next == null) return head;
        
        // 快慢指針找中點 (前半段較長)
        ListNode slow = head, fast = head, pre = null;
        while (fast != null && fast.next != null) {
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        pre.next = null; // 斷開
        
        ListNode l1 = mergeSort(head);
        ListNode l2 = mergeSort(slow);
        return merge(l1, l2);
    }
    
    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0), tail = dummy;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) { tail.next = l1; l1 = l1.next; }
            else { tail.next = l2; l2 = l2.next; }
            tail = tail.next;
        }
        tail.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }
}

進階解法：自底向上迭代歸併 (真正 O(1) 空間)

public ListNode sortList(ListNode head) {
    if (head == null || head.next == null) return head;
    
    // 計算長度
    int len = 0;
    for (ListNode p = head; p != null; p = p.next) len++;
    
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    
    for (int step = 1; step < len; step <<= 1) {
        ListNode prev = dummy, curr = dummy.next;
        while (curr != null) {
            ListNode left = curr;
            ListNode right = split(left, step);   // 切出左半段 step 長度
            curr = split(right, step);              // 切出右半段 step 長度
            prev = merge(prev, left, right);        // 合併並接回主鏈
        }
    }
    return dummy.next;
}

// 斷開前 n 個節點，返回剩餘鏈表頭
private ListNode split(ListNode head, int n) {
    for (int i = 1; head != null && i < n; i++) head = head.next;
    if (head == null) return null;
    ListNode next = head.next;
    head.next = null;
    return next;
}

// 合併 l1、l2 並接在 prev 後，返回合併後尾節點
private ListNode merge(ListNode prev, ListNode l1, ListNode l2) {
    ListNode tail = prev;
    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) { tail.next = l1; l1 = l1.next; }
        else { tail.next = l2; l2 = l2.next; }
        tail = tail.next;
    }
    tail.next = (l1 != null) ? l1 : l2;
    while (tail.next != null) tail = tail.next;
    return tail;
}