LeetCode LCR 026. 重排链表

2026-03-28 HGNULB 约 6 分钟

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

分类

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

标签

双指针 栈 LCR 链表 递归

题目描述

✅ LCR 026. 重排链表

题意分析

将非空链表 L0 → L1 → ... → Ln 重排为 L0 → Ln → L1 → Ln-1 → ...，依次从原链首、链尾交替取节点，直到全部用完。

需要实际改变节点连接，不能只交换值，也不创建替代节点。首节点仍然是原来的 L0，因此函数就地修改即可，不需要返回新头。单节点和双节点的顺序本来就满足要求。

解法：找中点、反转与交替合并

核心思路

[!blue]

前端节点可以顺序读取，难点是单链表无法从尾部倒着取。把后面一段反转后，原来的尾到头方向就变成了可顺序访问的方向，再与前段交替连接即可。

先用快慢指针找到切分位置。本实现两者都从 head 开始，循环到 fast 或它的后继为空，slow 在奇数长度时停于正中点，偶数长度时停于右中点。随后从 slow.next 切开，因此长度为 2k+1 时两段长 k+1、k；长度为 2k 时两段长 k+1、k-1。

偶数时并不是两半等长，但仍然正确：后段逆序后，先交替连接原两端的 k-1 对节点，前段最后剩下的两个节点正好是原来的中间两个，按原顺序接在末尾就是要求的最终一对。奇数时则剩下唯一的中点。

切开前先保存后段入口，再把中点的后继置空，得到两个不相交的节点序列。用普通迭代反转后段，每次先保存后继再改变方向。

合并时每轮先接前段一个节点、再接后段一个节点，并在覆盖连接前推进各自未处理入口。由于前段始终不少于后段，后段会先耗尽，最后把剩余前段直接接上。首个接入的仍是原头，调用方持有的头节点自然能遍历重排结果。

解题步骤

1. 快慢指针都从头开始，找出本实现定义的中点。
2. 先保存 mid.next，再令 mid.next = null，断开两段。
3. 原地反转后段，得到从原尾向中间的访问顺序。
4. 使用尾指针交替连接前段、反转后段的节点。
5. 后段耗尽后接上剩余前段，完成就地重排。

代码实现

class Solution {
    public void reorderList(ListNode head) {
        ListNode mid = middleNode(head);
        // 先存后继再断开，否则后半段丢失。
        ListNode tmp = mid.next;

        mid.next = null;
        tmp = reverseList(tmp);
        head = mergeTwoLists(head, tmp);
    }

    private ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        // 结束时 slow 停在前半段末尾，保证前半段不短于后半段。
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }

    private ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;

        while (cur != null) {
            ListNode tmp = cur.next;

            cur.next = pre;
            pre = cur;
            cur = tmp;
        }

        return pre;
    }

    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode();
        ListNode cur = dummy;

        // 固定「先接前半段、再接后半段」，对应 L0 → Ln → L1 → ...
        while (l1 != null && l2 != null) {
            cur.next = l1;
            l1 = l1.next;
            cur = cur.next;
            cur.next = l2;
            l2 = l2.next;
            cur = cur.next;
        }

        cur.next = l1 != null ? l1 : l2;

        return dummy.next;
    }
}

func reorderList(head *ListNode) {
    mid := middleNode(head)
    // 先存后继再断开，否则后半段丢失。
    tmp := mid.Next
    mid.Next = nil
    tmp = reverseList(tmp)
    head = mergeTwoLists(head, tmp)
}

func middleNode(head *ListNode) *ListNode {
    slow, fast := head, head
    // 结束时 slow 停在前半段末尾，保证前半段不短于后半段。
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }
    return slow
}

func reverseList(head *ListNode) *ListNode {
    var pre *ListNode
    cur := head
    for cur != nil {
        tmp := cur.Next
        cur.Next = pre
        pre = cur
        cur = tmp
    }
    return pre
}

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
    dummy := new(ListNode)
    cur := dummy
    // 固定「先接前半段、再接后半段」，对应 L0 → Ln → L1 → ...
    for l1 != nil && l2 != nil {
        cur.Next = l1
        l1 = l1.Next
        cur = cur.Next
        cur.Next = l2
        l2 = l2.Next
        cur = cur.Next
    }
    if l1 != nil {
        cur.Next = l1
    }
    if l2 != nil {
        cur.Next = l2
    }
    return dummy.Next
}

复杂度分析

• 时间复杂度：$O(n)$，找中点、反转、合并都是线性过程，依次执行不会相乘。
• 空间复杂度：$O(1)$，各过程只使用固定数量的指针及一个合并锚点。

关键点总结

[!green]

• 反转把尾部逆向读取转成顺向读取，再与原前段交替合并。
• 切分位置必须与实际快慢指针起点一致，本实现偶数长度取右中点。
• 前段剩一个或两个中间节点时，其现有顺序就是正确收尾。
• 只改变连接，所有原节点恰好使用一次，原头保持不变。

易错点总结

[!yellow]

• 先断开 mid.next 再读取它，会丢失后段入口，必须先暂存。
• 不能把这份代码讲成偶数长度两段等长；它保留右中点，前段比后段多两个节点。
• 合并时要在覆盖连接前保存或推进未处理后继，否则剩余节点可能无法再访问。
• 未切开两段就按这份合并流程操作，节点可能同时仍被两段引用，造成重复连接。
• 先接后段会改变要求的首尾顺序，应固定前段在先。

相似题目

题目	难度	关联与区别
876. 链表的中间结点	简单	快慢指针找中点是重排的第一步，之后才能拆成两半。
206. 反转链表	简单	反转后半段使尾部节点变得可顺序访问，再与前半段交替连接。

转载与许可

作者 HGNULB

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

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