LeetCode 143. 重排链表

约 5 分钟
文章信息 21 个分类 4 个标签
分类
LeetCode CodeTop 中等 已解决 需复习 200-500 字节跳动 微软 美团 阿里巴巴 快手 腾讯 猿辅导 百度 滴滴 拼多多 小米 商汤 虾皮 携程 哔哩哔哩
标签
双指针 栈 链表 递归
目录

题目描述

✅ 143. 重排链表

image-20230306130910150

image-20230306130914885

题意分析

给定单链表 L0 -> L1 -> ... -> Ln，要求原地重排成 L0 -> Ln -> L1 -> Ln-1 -> ...，也就是从两端向中间交替取节点。题目明确规定不能只修改节点值，必须通过调整节点之间的指针完成——这道题考察的就是指针操作本身。

约束透露的信号在于：单链表只能从头向后走，既不能随机访问，也拿不到任意节点的前驱，因此「从尾部取节点」不可能靠直接索引完成，必须先对链表做某种预处理换取按目标顺序取节点的能力。

边界上要留意：空链表和单节点链表无需任何操作；两节点链表重排后顺序不变。此外任何改动 next 的操作都可能丢失后续节点或制造环，动指针之前要想清楚需要先保存什么。

解法：找中点 + 反转后半段 + 交替合并

核心思路

目标顺序可以看成前半段与逆序后半段的交替合并。先用快慢指针找到中点并断链，再反转后半段，最后将两段链表交替连接，全程原地修改指针。

解题步骤

  • 快慢指针同时从头节点出发，找到前半段的尾节点 slow。
  • 从 slow.next 切出后半段，并将其反转。
  • 依次保存两段链表的后继，再把后半段节点插入前半段节点之后。
  • 后半段耗尽时结束；前半段长度不会更短，中间节点会自然留在末尾。

代码实现

class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }

        ListNode slow = head;
        ListNode fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode second = slow.next;
        slow.next = null;
        second = reverse(second);
        merge(head, second);
    }

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

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

        return pre;
    }

    private void merge(ListNode first, ListNode second) {
        while (second != null) {
            ListNode firstNext = first.next;
            ListNode secondNext = second.next;
            first.next = second;
            second.next = firstNext;
            first = firstNext;
            second = secondNext;
        }
    }
}

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

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

    second := slow.Next
    slow.Next = nil
    second = reverseList(second)
    mergeList(head, second)
}

func reverseList(head *ListNode) *ListNode {
    var pre *ListNode
    cur := head

    for cur != nil {
        next := cur.Next
        cur.Next = pre
        pre = cur
        cur = next
    }

    return pre
}

func mergeList(first *ListNode, second *ListNode) {
    for second != nil {
        firstNext := first.Next
        secondNext := second.Next
        first.Next = second
        second.Next = firstNext
        first = firstNext
        second = secondNext
    }
}

复杂度分析

  • 时间复杂度：$O(n)$，找中点、反转和合并各遍历一次链表。
  • 空间复杂度：$O(1)$，只使用常数个指针。

关键点总结

  • 找中点后必须断链，否则合并时可能形成环。
  • 修改 next 前先保存后继，避免丢失剩余链表。
  • 合并循环以后半段是否为空为条件，可统一处理奇偶长度。

易错点总结

  • 忘记执行 slow.next = null，会保留旧连接并可能形成环。
  • 改指针前没有保存后继，会丢失尚未处理的节点。
  • 快慢指针的循环边界写错，可能使后半段比前半段长。
  • 空链表或单节点链表未提前返回，会访问空指针。

相似题目

题目 难度 考察点
24. 两两交换链表中的节点 中等 相邻节点成对重连
25. K 个一组翻转链表 困难 分组反转与断链重接
92. 反转链表 II 中等 区间反转与前驱衔接
206. 反转链表 简单 迭代与递归反转基础
234. 回文链表 简单 找中点反转后对称比较
LCR 024. 反转链表 简单 反转模板的复刻练习
LCR 026. 重排链表 中等 本题镜像题，三段式组合
LCR 027. 回文链表 简单 回文判断的镜像练习
剑指 Offer 24. 反转链表 简单 反转链表的面试高频版
面试题 02.06. 回文链表 简单 回文判断加空间优化要求