LeetCode 148. 排序链表

◎

本节目标

用自底向上的归并排序在常数辅助空间内重排链表节点。

查看 LeetCode 原题

题意与边界

按升序重排单链表，目标时间复杂度为 O(n log n)、辅助空间为 O(1)。输出必须复用原节点；空链表与单节点链表直接保持不变。

自底向上归并

先统计长度，再依次合并长度为 1、2、4、... 的相邻有序段。split 截断并返回下一段开头，merge 返回合并后的头尾，主循环用前驱把结果接回整条链表。迭代版本不使用递归栈，满足常数辅助空间目标。

正确性依据

宽度为 w 的一轮开始时，每个长度不超过 w 的段已经有序。相邻两段经标准归并后成为长度不超过 2w 的有序段，且所有原节点恰好出现一次。宽度翻倍直到覆盖链表长度时，整条链表就是一个有序段。

代码实现

C++

C++17

#include <utility>
using namespace std;

class Solution {
private:
    ListNode* split(ListNode* head, int size) {
        for (int i = 1; i < size && head != nullptr; i++) {
            head = head->next;
        }
        if (head == nullptr) {
            return nullptr;
        }
        ListNode* second = head->next;
        head->next = nullptr;
        return second;
    }

    pair<ListNode*, ListNode*> merge(ListNode* left, ListNode* right) {
        ListNode dummy;
        ListNode* tail = &dummy;
        while (left != nullptr && right != nullptr) {
            if (left->val <= right->val) {
                tail->next = left;
                left = left->next;
            } else {
                tail->next = right;
                right = right->next;
            }
            tail = tail->next;
        }
        tail->next = left == nullptr ? right : left;
        while (tail->next != nullptr) {
            tail = tail->next;
        }
        return {dummy.next, tail};
    }

public:
    ListNode* sortList(ListNode* head) {
        int length = 0;
        for (ListNode* node = head; node != nullptr; node = node->next) {
            length++;
        }

        ListNode dummy(0, head);
        for (int width = 1; width < length; width *= 2) {
            ListNode* prev = &dummy;
            ListNode* cur = dummy.next;
            while (cur != nullptr) {
                ListNode* left = cur;
                ListNode* right = split(left, width);
                cur = split(right, width);
                auto [mergedHead, mergedTail] = merge(left, right);
                prev->next = mergedHead;
                prev = mergedTail;
            }
        }
        return dummy.next;
    }
};

Python

Python 3

from typing import Optional


class Solution:
    @staticmethod
    def _split(head: Optional[ListNode], size: int) -> Optional[ListNode]:
        for _ in range(1, size):
            if head is None:
                return None
            head = head.next
        if head is None:
            return None
        second = head.next
        head.next = None
        return second

    @staticmethod
    def _merge(left, right):
        dummy = ListNode()
        tail = dummy
        while left is not None and right is not None:
            if left.val <= right.val:
                tail.next = left
                left = left.next
            else:
                tail.next = right
                right = right.next
            tail = tail.next
        tail.next = right if left is None else left
        while tail.next is not None:
            tail = tail.next
        return dummy.next, tail

    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        length = 0
        node = head
        while node is not None:
            length += 1
            node = node.next

        dummy = ListNode(0, head)
        width = 1
        while width < length:
            prev = dummy
            cur = dummy.next
            while cur is not None:
                left = cur
                right = self._split(left, width)
                cur = self._split(right, width)
                merged_head, merged_tail = self._merge(left, right)
                prev.next = merged_head
                prev = merged_tail
            width *= 2
        return dummy.next

复杂度分析

• 时间复杂度：O(n log n)，每轮归并访问全部节点，共 O(log n) 轮。
• 空间复杂度：O(1)，所有重排都复用原节点和常数个指针。

易错点

• 使用自顶向下递归归并，时间正确但递归栈为 O(log n)。
• 切分第二段时忘记断开第一段，导致归并越过边界。
• 合并后只返回头节点，主循环不得不重复扫描或错误连接下一段。

模式迁移

链表不支持随机访问，却能用常数代价切分与拼接，因此归并排序是链表排序的自然选择。自底向上的倍增方式还可用于外部排序和按块合并。