Article / 文章
LeetCode 143 重排链表：三步优化空间复杂度到O(1)
给定一个单链表 L 的头节点 head ，单链表 L 表示为： L0 → L1 → L2 → ... → Ln-1 → Ln 请将其重新排列后变为： L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → ... 不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
题目描述
给定一个单链表 L 的头节点 head ，单链表 L 表示为：
L0 → L1 → L2 → … → Ln-1 → Ln
请将其重新排列后变为：
L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
难度
中等
不过掌握了思路后，其实也没那么难。关键是要把问题拆开来看，分成三个小问题。
题目链接
示例
示例 1：
输入：head = [1,2,3,4]
输出：[1,4,2,3]示例 2：
输入：head = [1,2,3,4,5]
输出：[1,5,2,4,3]提示
- 链表的长度范围为
[1, 5 * 10^4] 1 <= Node.val <= 1000
面试中怎么考
这题在面试里，面试官一般会这样问：
先问你能不能实现这个功能。这时候可以说线性表的方法，证明你有思路。
然后追问空间复杂度能不能优化到 O(1)。这时候就可以说三步法了。
有的面试官还会继续问，如果要求不破坏原链表怎么办？或者哪些地方容易出错？
面试的时候，如果能主动说出时间和空间复杂度，提出多种解法，说清楚边界条件怎么处理，会比较加分。代码写清楚，关键地方加注释也很重要。
解题思路
方法一：线性表
这是最容易想到的方法，虽然不是最优解，但面试时可以先说这个，让面试官知道你有思路。
核心思想很简单：既然链表不能随机访问，那就把它存到数组里！
具体就是用线性表存储链表的所有节点，然后利用数组可以下标访问的特点，按顺序取元素重建链表。
关键点：
- 使用列表存储所有节点
- 利用双指针从两端向中间遍历
- 重新连接节点
具体步骤：
- 遍历链表，将所有节点存入列表中
- 使用左右指针分别指向列表的两端
- 依次连接左右指针指向的节点
- 最后一个节点的next指向null
时间复杂度：O(n)，其中 n 是链表的长度。 空间复杂度：O(n)，需要使用线性表存储链表中的节点。
方法二：三步法（最优解）
这是面试官期待的答案，时间 O(n)，空间 O(1)。
这种方法不需要额外空间，分三个步骤：
- 找到原链表的中点（使用快慢指针）
- 将后半部分反转
- 将前半部分和反转后的后半部分合并
举个例子，链表 [1,2,3,4,5]：
- 找到中间，分成两堆：[1,2,3] 和 [4,5]
- 把后半堆翻转：[1,2,3] 和 [5,4]
- 交替合并：1→5→2→4→3
关键点：
- 用快慢指针找中点（快指针走2步，慢指针走1步）
- 反转后半部分（注意要先断开前后两部分）
- 交替合并两个链表（像拉链一样交叉连接）
具体步骤：
- 快慢指针找中点：慢指针每次走一步，快指针每次走两步，当快指针到末尾时，慢指针就在中点
- 从中点处断开链表，反转后半部分
- 前半部分和反转后的后半部分交替合并
复杂度分析：
- 时间复杂度：O(n)，其中 n 是链表的长度
- 空间复杂度：O(1)，只需要常数的额外空间
小技巧：写完代码后，可以主动说出“这个方法的优势是空间复杂度为 O(1)”，面试官会觉得你对算法有思考。
图解思路
方法一：线性表分析
以示例1为例：head = [1,2,3,4]
| 步骤 | 操作 | 链表状态 | 说明 |
|---|---|---|---|
| 初始状态 | 存储节点 | [1,2,3,4] | 将所有节点存入列表 |
| 第1步 | 连接1和4 | 1->4 | left=0, right=3 |
| 第2步 | 连接2和3 | 1->4->2->3 | left=1, right=2 |
| 第3步 | 设置结尾 | 1->4->2->3->null | 最后节点指向null |
方法二：三步法分析
以示例1为例：head = [1,2,3,4]
- 找到中点：
| 步骤 | 慢指针 | 快指针 | 说明 |
|---|---|---|---|
| 初始状态 | 1 | 1 | 同时指向头节点 |
| 第1步 | 2 | 3 | 慢走一步，快走两步 |
| 第2步 | 3 | null | 快指针到达末尾，慢指针指向中点 |
- 反转后半部分：
| 步骤 | 原链表 | 反转后 | 说明 |
|---|---|---|---|
| 初始状态 | 1->2 和 3->4 | 1->2 和 4->3 | 从中点断开，反转后半部分 |
- 合并链表：
| 步骤 | 操作 | 结果 | 说明 |
|---|---|---|---|
| 第1步 | 连接1和4 | 1->4 | 取前半部分第一个和后半部分第一个 |
| 第2步 | 连接2和3 | 1->4->2->3 | 取前半部分第二个和后半部分第二个 |
| 最终 | 完成合并 | 1->4->2->3->null | 设置结尾为null |
代码实现
C# 实现
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int val=0, ListNode next=null) {
* this.val = val;
* this.next = next;
* }
* }
*/
public class Solution {
public void ReorderList(ListNode head) {
if (head == null || head.next == null) {
return;
}
// 1. 找到中点
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// 2. 反转后半部分
ListNode mid = slow.next;
slow.next = null; // 断开前后两部分
ListNode prev = null;
while (mid != null) {
ListNode temp = mid.next;
mid.next = prev;
prev = mid;
mid = temp;
}
// 3. 合并两个链表
ListNode first = head;
ListNode second = prev;
while (second != null) {
ListNode temp1 = first.next;
ListNode temp2 = second.next;
first.next = second;
second.next = temp1;
first = temp1;
second = temp2;
}
}
}Python 实现
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reorderList(self, head: Optional[ListNode]) -> None:
"""
Do not return anything, modify head in-place instead.
"""
if not head or not head.next:
return
# 1. 找到中点
slow = fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
# 2. 反转后半部分
mid = slow.next
slow.next = None # 断开前后两部分
prev = None
while mid:
temp = mid.next
mid.next = prev
prev = mid
mid = temp
# 3. 合并两个链表
first = head
second = prev
while second:
temp1 = first.next
temp2 = second.next
first.next = second
second.next = temp1
first = temp1
second = temp2C++ 实现
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
void reorderList(ListNode* head) {
if (!head || !head->next) {
return;
}
// 1. 找到中点
ListNode* slow = head;
ListNode* fast = head;
while (fast->next && fast->next->next) {
slow = slow->next;
fast = fast->next->next;
}
// 2. 反转后半部分
ListNode* mid = slow->next;
slow->next = nullptr; // 断开前后两部分
ListNode* prev = nullptr;
while (mid) {
ListNode* temp = mid->next;
mid->next = prev;
prev = mid;
mid = temp;
}
// 3. 合并两个链表
ListNode* first = head;
ListNode* second = prev;
while (second) {
ListNode* temp1 = first->next;
ListNode* temp2 = second->next;
first->next = second;
second->next = temp1;
first = temp1;
second = temp2;
}
}
};性能分析
各语言实现的性能对比（LeetCode 实际测试）：
| 实现语言 | 执行用时 | 内存消耗 | 击败比例 |
|---|---|---|---|
| C++ | 36 ms | 17.4 MB | 95%+ |
| Python | 84 ms | 25.8 MB | 85%+ |
| C# | 92 ms | 42.1 MB | 80%+ |
从数据看：
- C++ 性能最好，指针操作效率高
- Python 代码最简洁，面试时写起来快
- C# 易读性不错，语法比较清晰
面试的话，Python 和 C++ 用得最多，建议至少掌握其中一种。
补充说明
代码亮点
面试时可以说说这几点：
- 一次遍历找中点：用快慢指针，避免了两次遍历
- 原地操作：不需要额外空间，空间复杂度优化到了 O(1)
- 临时变量技巧：合并时用 temp1、temp2 保存 next 节点，避免丢失引用。这个细节很多人会忽略
常见错误
1. 忘记断开前后两部分
// ❌ 错误写法
ListNode mid = slow.next;
// 忘记这一行！会导致前半部分还连着后半部分
// slow.next = null;
// ✅ 正确写法
ListNode mid = slow.next;
slow.next = null; // 必须断开！2. 反转链表时的空指针异常
// ❌ 容易出错的点
while (mid != null) {
mid.next = prev; // 如果这里先改了next
mid = mid.next; // 这里就丢失了原来的next！
}
// ✅ 正确做法：先用临时变量保存
while (mid != null) {
ListNode temp = mid.next; // 先保存！
mid.next = prev;
prev = mid;
mid = temp; // 再使用
}3. 合并时没有处理长度不等的情况
前半部分可能比后半部分多一个节点（奇数长度链表）。所以循环条件要用 while (second != null)，而不是 while (first != null && second != null)。
记忆技巧
可以用这个口诀：“找中点，断链表，翻后半，拉拉链”
- 找中点：快慢指针
- 断链表：slow.next = null
- 翻后半：反转链表
- 拉拉链：交替合并
相关题目
这道题用到的技巧，在这些题里也会用到：
| 题目 | 难度 | 关联 |
|---|---|---|
| 206. 反转链表 | 简单 | 用到反转操作 |
| 876. 链表的中间结点 | 简单 | 用到快慢指针找中点 |
| 234. 回文链表 | 简单 | 综合运用找中点+反转 |
| 21. 合并两个有序链表 | 简单 | 用到链表合并 |
讨论
有几个问题可以思考一下：
- 如果要求恢复原链表的结构（不破坏原链表），怎么做？
- 你在做这道题的时候遇到过什么坑？
- 这道题在实际工作中有没有用到的场景？
欢迎在评论区讨论。
如果你都看到这里了，说明还是有点收获的吧？给个赞鼓励一下呗。