148. 排序链表

对于链表排序问题，归并排序是一个很好的选择，因为它可以在 O(n log n) 时间复杂度内完成，并且非常适合链表结构。

代码实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        // 基本情况：空链表或只有一个节点的链表已经有序
        if (head == null || head.next == null) {
            return head;
        }
        
        // 使用快慢指针找到链表中点
        ListNode slow = head;
        ListNode fast = head.next;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // 将链表分成两半
        ListNode secondHalf = slow.next;
        slow.next = null;  // 断开链表
        
        // 递归排序两部分
        ListNode left = sortList(head);
        ListNode right = sortList(secondHalf);
        
        // 合并两个已排序的链表
        return merge(left, right);
    }
    
    private ListNode merge(ListNode l1, ListNode l2) {
        // 创建虚拟头节点
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        
        // 按升序合并两个链表
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }
        
        // 连接剩余部分
        current.next = (l1 != null) ? l1 : l2;
        
        return dummy.next;
    }
}

算法分析

• 时间复杂度：O(n log n)，其中 n 是链表的长度。归并排序的时间复杂度是 O(n log n)。
• 空间复杂度：O(log n)，主要来自递归调用栈的深度。

算法思路

1. 分治策略：将链表从中间分成两半，分别排序后再合并
2. 找中点：使用快慢指针技巧，快指针每次走两步，慢指针每次走一步
3. 递归排序：对两半链表分别递归调用排序函数
4. 合并操作：将两个已排序的子链表合并成一个有序链表

虽然递归归并排序已经非常高效，但自底向上（Bottom-up）的非递归归并排序可以进一步优化空间复杂度，避免递归调用栈的开销，特别适合处理非常长的链表。

代码实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        // 空链表或单节点链表直接返回
        if (head == null || head.next == null) {
            return head;
        }
        
        // 获取链表长度
        int length = 0;
        ListNode node = head;
        while (node != null) {
            length++;
            node = node.next;
        }
        
        // 创建虚拟头节点
        ListNode dummy = new ListNode(0, head);
        
        // 自底向上归并排序
        for (int subLength = 1; subLength < length; subLength <<= 1) {
            ListNode prev = dummy;
            ListNode curr = dummy.next;
            
            // 按当前子链表长度遍历整个链表
            while (curr != null) {
                // 获取第一个子链表
                ListNode head1 = curr;
                for (int i = 1; i < subLength && curr.next != null; i++) {
                    curr = curr.next;
                }
                
                // 获取第二个子链表
                ListNode head2 = curr.next;
                curr.next = null; // 断开第一个子链表
                curr = head2;
                
                // 移动到第二个子链表的末尾
                for (int i = 1; i < subLength && curr != null && curr.next != null; i++) {
                    curr = curr.next;
                }
                
                // 保存下一个起始节点并断开第二个子链表
                ListNode next = null;
                if (curr != null) {
                    next = curr.next;
                    curr.next = null;
                }
                
                // 合并两个子链表
                ListNode merged = merge(head1, head2);
                prev.next = merged;
                
                // 移动prev到合并后链表的末尾
                while (prev.next != null) {
                    prev = prev.next;
                }
                
                // 处理下一组子链表
                curr = next;
            }
        }
        
        return dummy.next;
    }
    
    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }
            current = current.next;
        }
        
        current.next = (l1 != null) ? l1 : l2;
        return dummy.next;
    }
}

算法优势

1. 空间复杂度优化：O(1)，不依赖递归栈，只使用固定数量的指针变量
2. 避免栈溢出：对于非常长的链表，递归实现可能导致栈溢出，而迭代实现无此限制
3. 缓存友好：迭代遍历模式对CPU缓存更友好，减少缓存未命中
4. 实际性能更好：虽然理论时间复杂度同样是O(n log n)，但常数因子更小，实际运行更快

算法思路

1. 先获取链表总长度，确定归并的轮次
2. 自底向上迭代：从小到大逐步合并子链表
   • 每轮合并前，链表被分成多个长度为subLength的有序子链表
   • 每轮将相邻的两个子链表合并
   • 每轮结束后，子链表长度翻倍
3. 精细化控制：精确管理指针，保持链表连接的完整性

这种方法在处理大规模链表排序时表现更佳，是工业级实现中更常用的方法。