LeetCode 补充题 123. 双向链表的常数空间排序

约 6 分钟
文章信息 3 个分类 2 个标签
分类
补充题 中等 字节
标签
链表 归并排序

题目描述

:::fold-green 相关原题

LeetCode 原题： ✅ 148. 排序链表

:::

给你一条无环双向链表，请原地将节点按值非降序排列，并返回排序后的头节点。

排序后，所有节点的 prev 和 next 指针都必须正确；值相等的节点需要保持原来的相对顺序。

你必须实现时间复杂度为 O(n log n)、额外空间复杂度为 O(1) 的算法。

示例 1：

输入： 双向链表 = [3,1,2]
输出： [1,2,3]
解释： 从新表头沿 next 访问为 1、2、3；从新表尾沿 prev 返回为 3、2、1。

提示：

  • 链表无环。
  • 要求 O(n log n) 时间、O(1) 额外空间。
  • next、prev 都必须正确。
  • 相同值的节点保持原相对顺序。

题意分析

链表无法常数时间随机访问，而归并只需顺序取节点，适合此结构。递归归并会使用调用栈，为满足额外空间 O(1)，改为从长度为 1 的有序段开始逐轮合并。

解法：自底向上归并并维护双向指针

核心思路

[!blue]

每轮开始时，链表可按长度 width 划成有序段。相邻两段归并后形成长度至多 2 * width 的有序段，下一轮将 width 翻倍；当段长覆盖全表时，整条链表有序。

合并前先记录左右段首、实际节点数以及后续入口 after。原链暂不切断，所以用 leftCount、rightCount 限制取值范围，不能仅以指针是否为空判断段是否耗尽。取出节点后先前进原段指针，再重接它的 prev 和结果尾节点的 next。

值相等时优先取左段，保留相同值节点的原始相对顺序。每轮首节点的 prev 设为空，最后一个节点的 next 也断开旧连接；整个过程只使用固定数量的指针和计数器。

解题步骤

  1. 统计链长，以 width=1 开始逐轮合并，width 每轮翻倍。
  2. 记录两段起点、实际节点数和下一段入口，再按剩余数量合并。
  3. 取节点前保存其 next，连接时同时更新 prev 与上一尾节点的 next。
  4. 每轮结束令新尾 next 为空，新头 prev 为空，返回最终有序链。

代码实现

class Node {
    int val;
    Node prev;
    Node next;

    Node(int val) {
        this.val = val;
    }
}

class Solution {
    public Node sortList(Node head) {
        int n = 0;

        for (Node p = head; p != null; p = p.next) {
            n++;
        }

        for (int width = 1; width < n; width = width > n / 2 ? n : width * 2) {
            Node current = head;
            Node newHead = null;
            Node tail = null;

            while (current != null) {
                Node left = current;
                Node right = current;
                int leftCount = 0;
                int rightCount = 0;

                for (; leftCount < width && right != null; leftCount++) {
                    right = right.next;
                }

                Node after = right;

                for (; rightCount < width && after != null; rightCount++) {
                    after = after.next;
                }

                while (leftCount > 0 || rightCount > 0) {
                    Node picked;

                    if (rightCount == 0 || leftCount > 0 && left.val <= right.val) {
                        picked = left;
                        left = left.next;
                        leftCount--;
                    } else {
                        picked = right;
                        right = right.next;
                        rightCount--;
                    }

                    picked.prev = tail;

                    if (tail == null) {
                        newHead = picked;
                    } else {
                        tail.next = picked;
                    }

                    tail = picked;
                }

                current = after;
            }

            tail.next = null;
            head = newHead;
        }

        if (head != null) {
            head.prev = null;
        }

        return head;
    }
}

type Node struct {
    Val        int
    Prev, Next *Node
}

func sortList(head *Node) *Node {
    n := 0
    for p := head; p != nil; p = p.Next {
        n++
    }
    for width := 1; width < n; {
        current := head
        var newHead, tail *Node
        for current != nil {
            left, right := current, current
            leftCount, rightCount := 0, 0
            for leftCount < width && right != nil {
                right = right.Next
                leftCount++
            }
            after := right
            for rightCount < width && after != nil {
                after = after.Next
                rightCount++
            }
            for leftCount > 0 || rightCount > 0 {
                var picked *Node
                if rightCount == 0 || leftCount > 0 && left.Val <= right.Val {
                    picked = left
                    left = left.Next
                    leftCount--
                } else {
                    picked = right
                    right = right.Next
                    rightCount--
                }
                picked.Prev = tail
                if tail == nil {
                    newHead = picked
                } else {
                    tail.Next = picked
                }
                tail = picked
            }
            current = after
        }
        tail.Next = nil
        head = newHead
        if width > n/2 {
            width = n
        } else {
            width *= 2
        }
    }
    if head != nil {
        head.Prev = nil
    }
    return head
}

复杂度分析

  • 时间复杂度：$O(n \log n)$。
  • 空间复杂度：额外空间 $O(1)$。

关键点总结

[!green]

按段内剩余数量控制合并，避免重接指针后跨入下一段；相等时先取左段，保证节点身份顺序稳定。

易错点总结

[!yellow]

单向next有序不代表双向链表正确，需同时核对每条prev；先保存下一段入口，避免重连指针后丢失后续段。

相似题目

题目 难度 关联与区别
148. 排序链表 中等 复用迭代归并得到常数辅助空间，本题每次连接还必须维护 prev。
21. 合并两个有序链表 简单 两段有序链的稳定合并是核心子过程；双向版本同时重接前驱并保存下一段入口。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/80063184
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！