归并排序链表实战：LeetCode148迭代O(1)空间解法

本文讲解如何在 [O(nlogn)] 时间复杂度下对链表排序，并尽量将额外空间控制到常数级。核心思路是使用 bottom-up（自底向上）归并排序，用迭代替代递归，从而避免递归栈带来的 [O(logn)] 额外空间。重点拆解两个关键操作：cut（断链切分）与 merge（合并有序链表）。

题目描述

在 [O(nlogn)] 时间复杂度和常数级空间复杂度下，对链表进行排序。

输入: 4->2->1->3
输出: 1->2->3->4

解题思路：为什么选 bottom-up 归并排序

最直接的做法是把链表节点放入数组排序，再重建链表，但这会引入额外 [O(n)] 空间，不满足要求。

从复杂度目标 [O(nlogn)] + [O(1)] 出发，自然联想到 归并排序：

• 数组归并需要额外数组空间；
• 链表归并可以通过调整指针原地重排，省掉“数组额外空间”。

真正棘手的是：递归版归并排序会带来 [O(logn)] 的递归栈空间。要把空间压到 [O(1)]，就需要把“递归切分”改成“迭代切分”，这就是 bottom-up 的价值。

想系统刷类似题型（链表切分、归并、指针操作），可以配合云栈的算法/数据结构专题一起练。

bottom-up 的整体过程

bottom-up 的归并排序思路：先按 1 个节点一组两两 merge；再按 2 个一组 merge；再按 4 个一组……直到 step 覆盖整个链表。

例如：[4,3,1,7,8,9,2,11,5,6]

step=1: (3->4)->(1->7)->(8->9)->(2->11)->(5->6)
step=2: (1->3->4->7)->(2->8->9->11)->(5->6)
step=4: (1->2->3->4->7->8->9->11)->5->6
step=8: (1->2->3->4->5->6->7->8->9->11)

链表操作里最难的往往不是排序思想，而是“断链 + 挂接”。这里主要用到三件事：

• merge(l1, l2)：合并两个有序链表（常规双指针）
• cut(l, n)：把链表 l 切掉前 n 个节点，并返回“后半段”的头指针
• dummyHead：哑结点简化头节点处理，减少边界条件

这些技巧也是很多面试链表题的通用套路。

伪代码（理解整体框架）

current = dummy.next
tail = dummy

for step = 1; step < length; step *= 2:
    while current:
        left = current
        right = cut(current, step)
        current = cut(right, step)

        tail.next = merge(left, right)
        while tail.next:
            tail = tail.next

迭代版（bottom-up）参考实现：常数级额外空间

语言：C++
说明：通过迭代 step（1,2,4,8...）逐层归并，避免递归栈开销。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        ListNode dummyHead(0);
        dummyHead.next = head;

        // 先统计长度
        int length = 0;
        auto p = head;
        while (p) {
            ++length;
            p = p->next;
        }

        // step = 1, 2, 4, 8...
        for (int step = 1; step < length; step <<= 1) {
            auto cur = dummyHead.next;
            auto tail = &dummyHead;

            // 每次从 cur 开始，切出 left/right 两段各 step 长度，merge 后挂回 tail
            while (cur) {
                auto left = cur;
                auto right = cut(left, step);     // left: step 个
                cur = cut(right, step);           // right: step 个，cur 指向下一段起点

                tail->next = mergeTwoLists(left, right);

                // tail 移动到当前已合并段的末尾
                while (tail->next) {
                    tail = tail->next;
                }
            }
        }
        return dummyHead.next;
    }

    // cut：将 head 链表切掉前 n 个节点，返回剩余部分的头指针
    // 切分后：原 head 成为一条独立链（尾部 next=null），返回 next 作为后半段
    ListNode* cut(ListNode* head, int n) {
        auto p = head;
        while (--n && p) {
            p = p->next;
        }
        if (!p) return nullptr;

        auto next = p->next;
        p->next = nullptr;  // 断链
        return next;
    }

    // 合并两个有序链表（非递归）
    ListNode* mergeTwoLists(ListNode* pHead1, ListNode* pHead2) {
        ListNode* pNode = new ListNode(-1);
        ListNode* dummyHead = pNode;

        while (pHead1 != nullptr && pHead2 != nullptr) {
            if (pHead1->val < pHead2->val) {
                pNode->next = pHead1;
                pHead1 = pHead1->next;
            } else {
                pNode->next = pHead2;
                pHead2 = pHead2->next;
            }
            pNode = pNode->next;
        }

        pNode->next = (pHead1 == nullptr) ? pHead2 : pHead1;
        return dummyHead->next;
    }
};

![](https://static1.yunpan.plus/attachment/453e934155ad.png)

参考代码：递归版（更好写，但空间不达标）

递归版归并排序思路清晰，面试中若写不出最优解，先写它也能拿到不错的分数。但它会引入递归栈空间 [O(logn)]，严格来说不满足“常数级空间”。

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        // 递归出口
        if (head == nullptr || head->next == nullptr) {
            return head;
        }

        // 快慢指针找中点
        // 注意：fast 从 head->next 开始，避免偶数长度时 slow 停在右中位导致无限递归
        ListNode* fast = head->next;
        ListNode* slow = head;
        while (fast != nullptr && fast->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
        }

        // 断链分成两段
        ListNode* tmp = slow->next;
        slow->next = nullptr;

        // 递归排序 + 合并
        ListNode* left = sortList(head);
        ListNode* right = sortList(tmp);
        return mergeTwoLists(left, right);
    }

    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* pDummy = new ListNode(-1);
        ListNode* pNode = pDummy;

        while (l1 != nullptr && l2 != nullptr) {
            if (l1->val <= l2->val) {
                pNode->next = l1;
                l1 = l1->next;
            } else {
                pNode->next = l2;
                l2 = l2->next;
            }
            pNode = pNode->next;
        }

        pNode->next = (l1 == nullptr) ? l2 : l1;
        return pDummy->next;
    }
};

![](https://static1.yunpan.plus/attachment/453e934155ad.png)

小结：实现 bottom-up 的关键点

• step 每轮翻倍（1,2,4,8...），代表“每段长度”
• cut 必须正确断链，否则会形成环或导致合并结果混乱
• tail 必须始终指向已处理部分的尾结点，保证下一次挂接位置正确

如果你在 cut/merge/tail 的指针细节上容易出错，建议把每一轮 step 的链表状态画出来对照调试，效果非常明显。
更多同类题的归并、链表指针套路，也可以在算法/数据结构里做系统整理与专项训练。