LeetCode LCR 077. 排序链表

2026-03-28 HGNULB 约 10 分钟

文章信息 5 个分类 6 个标签

分类

LeetCode 中等 119 经典题变种挑战剑指 Offer 剑指 Offer（专项突击版）

题目描述

✅ LCR 077. 排序链表

题意分析

将单链表按节点值升序排列，返回排序后的头节点。链表可能为空，节点也可能有相同值；可以复用节点并修改 next 指针。

进阶要求 $O(n\log n)$ 时间和 $O(1)$ 额外空间。归并排序适合链表，因为合并两条有序链只需要顺序移动指针。递归版使用 $O(\log n)$ 调用栈；下面再给出满足常数空间要求的迭代版。

解法：递归归并排序链表

核心思路

[!blue]

若能把两半分别排好序，就能不断比较两个头节点，将较小者接到结果末尾，在线性时间内合并。因此先把链表拆成两半，递归排序，再合并。

sortList(head) 返回当前链段排序后的头节点。空链表和单节点已经有序，直接返回。其余情况用快慢指针找前半段的尾节点：slow 从头开始每次一步，fast 从第二个节点开始每次两步，使两段长度尽量接近，且都短于原链表。

找到中点后，先保存 rightHead = slow.next，再断开 slow.next。只有真正断链，左右递归才会处理各自的半段。两段排好后，用哨兵 dummy 和尾指针 tail 合并；一条耗尽时，另一条剩余部分本身有序，可以整体接上。

解题步骤

当前链表为空或只有一个节点时，直接返回。

用快慢指针找到前半段尾节点，保存右半段入口后断链。

分别递归排序左右两段。

每次取两条有序链中较小的头节点，接到结果尾部；最后接上未耗尽的一段，返回 dummy.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;
        }

        // slow 是左半段尾节点，断开后左右两段才能独立递归。
        ListNode rightHead = slow.next;

        slow.next = null;

        ListNode left = sortList(head);
        ListNode right = sortList(rightHead);

        return merge(left, right);
    }

    private ListNode merge(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;

        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                tail.next = list1;
                list1 = list1.next;
            } else {
                tail.next = list2;
                list2 = list2.next;
            }

            tail = tail.next;
        }

        if (list1 != null) {
            tail.next = list1;
        } else {
            tail.next = list2;
        }

        return dummy.next;
    }
}

func sortList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    slow := head
    fast := head.Next
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }

    // 断开左右两段，避免左半段递归时继续连到右半段。
    rightHead := slow.Next
    slow.Next = nil

    left := sortList(head)
    right := sortList(rightHead)
    return mergeSortedLists(left, right)
}

func mergeSortedLists(list1 *ListNode, list2 *ListNode) *ListNode {
    dummy := &ListNode{}
    tail := dummy

    for list1 != nil && list2 != nil {
        if list1.Val <= list2.Val {
            tail.Next = list1
            list1 = list1.Next
        } else {
            tail.Next = list2
            list2 = list2.Next
        }
        tail = tail.Next
    }
    if list1 != nil {
        tail.Next = list1
    } else {
        tail.Next = list2
    }

    return dummy.Next
}

复杂度分析

时间复杂度：$O(n\log n)$。切分层数为 $O(\log n)$，每层切分和合并的总工作量为 $O(n)$。

空间复杂度：$O(\log n)$，来自递归调用栈；排序复用原节点。

关键点总结

[!green]

递归先保证两段有序，合并时只需比较它们当前最小的头节点。

先保存右半段入口，再断链，既不丢节点，也保证子问题严格缩小。

递归版并非常数空间，进阶要求需要下面的迭代写法。

解法二：自底向上归并排序链表

核心思路

[!blue]

单个节点天然有序。先把相邻的两个长度为 1 的链段合并，再合并长度为 2、4、8 的链段，每轮把有序段长度翻倍。这样用循环控制合并层数，不再需要递归栈。

每轮开始时，链表由长度至多为 size 的有序段组成，最后一段可以更短。用 split 依次切出左右两段，并在改接指针前保存下一组入口 current。合并这两段后接到本轮结果尾部，得到长度至多为 2 * size 的有序段。

split(head, size) 最多切出 size 个节点，断开段尾并返回剩余链头；节点不足时保留实际长度，右段也允许为空。merge(left, right, tail) 将两段接到给定尾节点之后，并返回新的真实段尾，供下一组继续接入。

当 size >= length，整条链表已是一段有序链。所有操作只使用固定数量的指针和一个哨兵节点，因此额外空间为常数。

解题步骤

扫描链表得到总长度 length，创建指向原头节点的哨兵。

从 size = 1 开始，每轮令 tail 回到哨兵，current 回到当前链头。

连续切出至多 size 个节点的左段、右段，并保存下一组入口。

合并两段，接到 tail 后，将 tail 更新到合并段末尾。

当前轮处理完后将 size 翻倍，最终返回哨兵的后继。

代码实现

class Solution {
    public ListNode sortList(ListNode head) {
        int length = 0;

        for (ListNode node = head; node != null; node = node.next) {
            length++;
        }

        ListNode dummy = new ListNode(0);

        dummy.next = head;

        for (int size = 1; size < length; size <<= 1) {
            ListNode tail = dummy;
            ListNode current = dummy.next;

            while (current != null) {
                ListNode left = current;
                ListNode right = split(left, size);

                current = split(right, size);
                tail = merge(left, right, tail);
            }
        }

        return dummy.next;
    }

    private ListNode split(ListNode head, int size) {
        for (int i = 1; head != null && i < size; i++) {
            head = head.next;
        }

        if (head == null) {
            return null;
        }

        ListNode next = head.next;

        head.next = null;

        return next;
    }

    private ListNode merge(ListNode left, ListNode right, ListNode tail) {
        while (left != null && right != null) {
            if (left.val <= right.val) {
                tail.next = left;
                left = left.next;
            } else {
                tail.next = right;
                right = right.next;
            }

            tail = tail.next;
        }

        tail.next = left != null ? left : right;

        while (tail.next != null) {
            tail = tail.next;
        }

        return tail;
    }
}

func sortList(head *ListNode) *ListNode {
    length := 0
    for node := head; node != nil; node = node.Next {
        length++
    }

    dummy := &ListNode{Next: head}
    for size := 1; size < length; size <<= 1 {
        tail := dummy
        current := dummy.Next

        for current != nil {
            left := current
            right := splitList(left, size)
            current = splitList(right, size)
            tail = mergeSortedLists(left, right, tail)
        }
    }
    return dummy.Next
}

func splitList(head *ListNode, size int) *ListNode {
    for i := 1; head != nil && i < size; i++ {
        head = head.Next
    }
    if head == nil {
        return nil
    }

    next := head.Next
    head.Next = nil
    return next
}

func mergeSortedLists(left, right, tail *ListNode) *ListNode {
    for left != nil && right != nil {
        if left.Val <= right.Val {
            tail.Next = left
            left = left.Next
        } else {
            tail.Next = right
            right = right.Next
        }
        tail = tail.Next
    }
    if left != nil {
        tail.Next = left
    } else {
        tail.Next = right
    }
    for tail.Next != nil {
        tail = tail.Next
    }
    return tail
}

复杂度分析

时间复杂度：$O(n\log n)$。每轮切段、归并及寻找段尾只让节点被访问常数次，共 $O(\log n)$ 轮。

空间复杂度：$O(1)$，无递归，也不创建辅助数组。

关键点总结

[!green]

轮初每段已排序，合并相邻两段后，有序段长度翻倍。

改接链表前先保存下一组入口，避免后续节点丢失。

最后一组不足两段时，切分和归并函数也能直接处理，无需补节点。

易错点总结

[!yellow]

递归切分必须断链；快指针从 head.next 开始，才能让两节点链表也分成更小的子问题。

迭代切段要在修改连接前保存下一组入口，不能沿合并后改变的旧指针寻找它。

合并后应返回真实尾节点，包含直接接上的剩余后缀，否则下一组可能覆盖已有节点。

空链表和单节点不需要合并；常数空间要求不能忽略递归栈。

相似题目

题目	难度	关联与区别
21. 合并两个有序链表	简单	排序的合并阶段复用两条有序链表归并，分治再负责把原链表拆成更小段。

.article-image.is-loading { width: var(--article-image-width, 100%); height: auto; } .article-image.is-loading img { position: static; width: auto !important; height: auto !important; opacity: 1; pointer-events: auto; } .article-image-spinner { display: none; }

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/22754907

许可本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！