type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
输入是一个单向链表
L的头节点head。单向链表
L表示为:请将其重新排列后变为:
不能只是改变节点的值,而是需要实际的交换节点。
示例 1:

示例 2:

解法一:快慢指针(推荐)
- 快慢指针找中点
想象快指针走两步、慢指针走一步。
快指针到头时,慢指针正好在链表中间附近。
中点的下一位,就是“后半段链表”的起点。
- 把后半段链表整个反转
因为我们想从后往前拿元素,但链表不能反向走,所以干脆把后半段整个翻转,这样你就能从新头节点一路向右走,等价于“从后往前取”。
- 两段链表交替合并
前半段:1 → 2 → 3
反转后半段:5 → 4
每次把后半段节点插到前半段节点后面,就形成了想要的顺序。
复杂度
- 时间:O(n) 三次线性遍历(找中点、反转、合并)
- 空间:O(1)
解法二:栈
- 把链表所有节点丢进栈
栈的特点是后进先出,也就是说你可以轻松从链表尾部不断弹出节点。
- 从头开始走链表,每次取一个栈顶插回链表
但要注意,只需要弹出链表后半段的数量。
例如链表长度为
n,只需要弹出 (n − 1) // 2 个节点。- 边插边移动指针
直到处理完后半部分,最后把尾节点的 next 指向 None。
思路简单,不过需要 O(n) 额外空间。
复杂度
- 时间:O(n)
- 空间:O(n)
解法三:数组 + 双指针
- 把所有节点丢进数组
- 双指针 left 从开头走,right 从末尾走
- 每次交替取节点,重新连接它们
这跟栈方法差不多,写起来简单,也需要用 O(n) 空间。
复杂度
- 时间 O(n)
- 空间 O(n)
- 作者:Fan Luo
- 链接:https://fanluo.me/article/leetcode-143-重排链表
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处。
上一篇
[Leetcode 138] 随机链表的复制
下一篇
[Leetcode 146] LRU 缓存