在这篇文章中，我们将深入探讨一个在技术面试中极具挑战性但也非常经典的链表问题——链表重排（Reorder List）。这不仅仅是一道算法题，更是检验我们对于链表操作基本功的试金石。我们将从零开始，通过拆解问题、分析思路，最终编写出优雅且高效的代码。无论你是正在准备面试，还是希望精进自己的数据结构功底，这篇文章都将为你提供详尽的实战指南。
问题描述：我们在面对什么？
首先，让我们明确一下目标。给定一个单链表 L，我们需要对其进行“原地”重排，具体规则如下：
- 第一个节点保持不变，作为新链表的第 1 个节点。
- 最后一个节点变为新链表的第 2 个节点。
- 原链表的第二个节点变为新链表的第 3 个节点。
- 原链表的倒数第二个节点变为新链表的第 4 个节点。
- 以此类推，直到没有剩余节点。
规则总结： 如果我们用 INLINECODE3ffc9fee 来表示原链表，那么重排后的形式应该是 INLINECODE5218fdcd。
这种操作会改变链表的结构，要求我们不能只是简单地打印值，而是要真正修改节点的 next 指针。由于题目通常要求“原地”操作（即空间复杂度为 O(1)），这意味着我们不能简单地创建一个新链表来存储结果，必须在原链表上通过指针的“腾挪”来完成。
示例说明：直观理解
为了让你对问题有更直观的感受，让我们来看几个具体的例子。
示例 1：奇数个节点
输入：
链表：1 -> 2 -> 3 -> 4 -> 5
输出：
重排后的链表：1 -> 5 -> 2 -> 4 -> 3
解析：
- 第 1 个节点是 INLINECODE511e6a95，最后 1 个节点是 INLINECODE20c479e8。
- 第 2 个节点是 INLINECODE80191f48，倒数第 2 个节点是 INLINECODEd36448be。
- 剩下的中间节点是
3，直接放在末尾。
示例 2：偶数个节点
输入：
链表：1 -> 2 -> 3 -> 4 -> 5 -> 6
输出：
重排后的链表：1 -> 6 -> 2 -> 5 -> 3 -> 4
解析：
- 第 1 个是 INLINECODE0d65be55，最后 1 个是 INLINECODEad5dc306。
- 第 2 个是 INLINECODE30ffd5f6，倒数第 2 个是 INLINECODE20d14517。
- 第 3 个是 INLINECODEa80d1905，倒数第 3 个是 INLINECODE71fc7a9e。
- 刚好用完，拼接完成。
解题思路：化繁为简的艺术
面对这种看似复杂的指针操作问题，如果我们试图一步到位，很容易被指针的跳跃搞得晕头转向。作为有经验的开发者，我们的策略应该是“分而治之”。我们可以将这个宏大的重排任务，拆解为三个标准的、独立的链表子问题。只要你掌握了这三个基本功，这道题就迎刃而解了。
这三个核心步骤是：
- 寻找中间节点：将链表从中间断开，分为前半部分和后半部分。
- 反转链表：将后半部分链表进行原地反转，这样原来的尾部节点就变成了头节点，方便我们按顺序取用。
- 合并链表：将前半部分链表和“反转后的后半部分链表”进行交替合并。
核心概念与实现细节
在编写代码之前，让我们深入探讨一下这三个步骤的技术细节。
#### 1. 寻找链表中点：快慢指针法
这是链表算法中最经典的技术之一。我们要找的是链表的“中间偏后”的那个节点，以便把后半部分切出来。
原理：
我们维护两个指针，INLINECODEf18f2658 和 INLINECODE86b25000。
slow指针每次走一步。fast指针每次走两步。
当 INLINECODEf20445a8 指针无法继续移动时（到达链表末尾），INLINECODE79ba8646 指针正好走了一半的路程，位于中间位置。
实现要点：
这里有一个小细节需要注意。对于偶数个节点的链表（如 1 -> 2 -> 3 -> 4），我们希望断开位置是在 2 之后。所以，循环条件通常设为 INLINECODE5773cca1。这样当循环结束时，INLINECODEef3ab1b5 指向的就是前半部分的最后一个节点。
#### 2. 反转链表：迭代法
反转链表是必须熟练掌握的技能。我们的目标是将 INLINECODE56fd7daa 变成 INLINECODE22025e39。
原理：
我们需要遍历链表，并在遍历过程中修改每个节点的 next 指针，使其指向前一个节点。为此，我们需要维护三个指针：
prev：记录前一个节点（初始为 None）。curr：当前正在处理的节点。- INLINECODEa1bed6dc：暂存下一个节点，防止因为修改 INLINECODE0e05f79c 而导致链表断裂。
逻辑：
INLINECODEa326512b 指向 INLINECODE171862dd，然后 INLINECODEa7b44836 和 INLINECODE40fa16d9 都向后移一位。
#### 3. 交替合并两个链表
现在我们有了两个链表头：INLINECODE55d08c8e（前半部分）和 INLINECODE13a053ff（反转后的后半部分）。我们需要把它们缝在一起。
逻辑：
只要这两个链表都还有节点，我们就进行如下操作：
- 保存 INLINECODEa0ea7256 的下一个节点（INLINECODEe8a087c0）。
- 保存 INLINECODE4094bd81 的下一个节点（INLINECODE38d7623a）。
- 将 INLINECODE63cccee2 指向 INLINECODEf80437c5（
head1.next = head2）。 - 将 INLINECODE448d3433 指向刚才保存的 INLINECODE9845f154（
head2.next = temp1）。 - 更新 INLINECODE1e286b16 和 INLINECODE244c8bb9，移动到下一轮的起始位置（INLINECODE4a763dd3, INLINECODEde89f51d）。
算法实现：完整的 Python 代码
让我们将上述思路转化为代码。请仔细阅读代码中的注释，理解每一步的指针变化。
# 定义链表节点
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reorderList(head):
"""
主函数：重排链表
"""
# 边界条件检查：如果链表为空或只有一个节点，无需重排
if not head or not head.next:
return head
# --- 步骤 1: 使用快慢指针寻找中间节点 ---
# 初始化慢指针和快指针都指向头节点
slow, fast = head, head
# 注意循环条件：
# fast.next 检查是否为奇数节点（停在最后一个节点）
# fast.next.next 检查是否为偶数节点（停在倒数第二个节点）
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
# 此时 slow 指向的是前半部分的最后一个节点
# 例如：1->2->3->4->5，slow指向3
# 例如：1->2->3->4，slow指向2
# --- 步骤 2: 反转后半部分链表 ---
# 我们需要反转 slow.next 之后的链表
prev, curr = None, slow.next
# 关键一步：断开前半部分和后半部分的连接
# 这样我们就有了两个独立的链表
slow.next = None
# 标准反转链表操作
while curr:
next_temp = curr.next # 暂存下一个节点
curr.next = prev # 反转指针
prev = curr # prev 前移
curr = next_temp # curr 前移
# 循环结束后，prev 指向的是反转后链表的头节点（原链表的尾节点）
# --- 步骤 3: 合并两个链表 ---
# first 指向前半部分的头，second 指向反转后的后半部分的头
first, second = head, prev
# 只要 second 不为空，就进行交替合并
# 注意：如果是奇数个节点，first 链表比 second 多一个节点，循环结束正好处理完
while second:
# 暂存两个链表的下一个节点，防止指针丢失
temp1 = first.next
temp2 = second.next
# 交叉连接：first -> second
first.next = second
# 交叉连接：second -> 原来的 first.next
second.next = temp1
# 移动指针到下一轮待处理的位置
first = temp1
second = temp2
return head
# 辅助函数：打印链表用于验证
def printList(head):
res = []
while head:
res.append(str(head.val))
head = head.next
print(" -> ".join(res))
# 测试代码
def run_tests():
# 测试用例 1: 奇数个节点
print("--- 测试用例 1 (奇数) ---")
n1 = ListNode(1)
n2 = ListNode(2)
n3 = ListNode(3)
n4 = ListNode(4)
n5 = ListNode(5)
n1.next, n2.next, n3.next, n4.next = n2, n3, n4, n5
print("输入:")
printList(n1)
reorderList(n1)
print("输出:")
printList(n1)
print()
# 测试用例 2: 偶数个节点
print("--- 测试用例 2 (偶数) ---")
l1 = ListNode(1)
l2 = ListNode(2)
l3 = ListNode(3)
l4 = ListNode(4)
l5 = ListNode(5)
l6 = ListNode(6)
l1.next, l2.next, l3.next = l2, l3, l4
l4.next, l5.next = l5, l6
print("输入:")
printList(l1)
reorderList(l1)
print("输出:")
printList(l1)
print()
# 测试用例 3: 只有1个节点
print("--- 测试用例 3 (单节点) ---")
s1 = ListNode(99)
print("输入:")
printList(s1)
reorderList(s1)
print("输出:")
printList(s1)
if __name__ == "__main__":
run_tests()
代码执行流程图解
为了让你的理解更加深刻，让我们手动模拟一下代码在处理 1 -> 2 -> 3 -> 4 -> 5 时的内部状态变化。
初始状态：
head -> 1 -> 2 -> 3 -> 4 -> 5 -> None
阶段一：寻找中点
- INLINECODEaf5ce07c 和 INLINECODE2a623129 从 1 开始。
- 第一轮：INLINECODE96fd3074 到 2，INLINECODEc5ef1de6 到 3。
- 第二轮：INLINECODE87aaf151 到 3，INLINECODEb7abc922 到 5。
- 第三轮：INLINECODE348e1311 无法再走两步（INLINECODEc1069aa9 是 None），循环结束。
- 此时
slow指向节点 3。
阶段二：反转后半部分
- INLINECODE71ac8ff1 指向 INLINECODEa09a2c3b，即节点 4。
- INLINECODE890c6e23。链表变为：INLINECODE763d9a25 和
4 -> 5。 - 开始反转
4 -> 5：
– 处理 4：INLINECODEeacd5044 指向 None。变成 INLINECODE893407ac。INLINECODE0d235852 变为 4。INLINECODEd10471bb 变为 5。
– 处理 5：INLINECODEd417c209 指向 4。变成 INLINECODE3cf4a212。INLINECODEf0cb3289 变为 5。INLINECODEdc15a0e5 变为 None。
- 反转结束，
prev指向节点 5（新头）。 - 当前状态：链表 A (INLINECODE6a7b9e50)，链表 B (INLINECODE3bffb2e4)。
阶段三：合并
- INLINECODE420c4941 = 1, INLINECODE034eb179 = 5。
- 第一轮：
– temp1 = 2 (1 的下一个)。
– temp2 = 4 (5 的下一个)。
– 1.next = 5。
– 5.next = 2。
– 结果：1 -> 5 -> 2 -> ... (3 连着 2，4 连着 5，已经被断开了吗？不，之前 slow.next=None 断开了，且反转时断开了)。
– 正确连接后：INLINECODE8ed3271e 变为 2，INLINECODEff8105e6 变为 4。
- 第二轮：
– temp1 = 3 (2 的下一个)。
– temp2 = None (4 的下一个)。
– 2.next = 4。
– 4.next = 3。
– INLINECODEc092580f 变为 3，INLINECODE8654c6c7 变为 None。
- 循环结束：因为
second为 None。 - 最终链条：1 -> 5 -> 2 -> 4 -> 3。完美匹配。
复杂度分析
让我们来评估一下这个解决方案的效率。
- 时间复杂度：O(N)。
我们遍历链表寻找中点（约 N/2 步），遍历后半部分进行反转（约 N/2 步），最后遍历整个链表进行合并（N 步）。虽然我们遍历了多次，但总体的步数仍然是与节点总数 N 成正比的。常数项被忽略，所以是 O(N)。
- 空间复杂度：O(1)。
这是本解法的亮点。我们没有使用任何额外的数组或哈希表来存储节点，仅仅使用了几个指针变量（INLINECODE51db743f, INLINECODEdcbfd1da, INLINECODE724ade41, INLINECODE3c917872, INLINECODE54b992ce, INLINECODE3f84018e）。无论链表有多长，这些变量的数量都是固定的。这完美符合“原地修改”的要求。
常见错误与最佳实践
在实际编码和面试中，开发者往往会在以下细节上栽跟头。
1. 忘记断开链表
在找到中间节点 INLINECODE93fde7e1 后，如果直接把 INLINECODE476d806c 拿去反转，而不执行 slow.next = None，那么前半部分的链表末尾仍然连接着原来的后半部分节点。这会导致在合并阶段形成环，或者导致结构混乱。一定要记得“断开”旧连接，才能建立新连接。
2. 指针丢失
在合并两个链表时，新手容易犯的错误是直接写 INLINECODE876e091e，然后马上想移动 INLINECODE0b560c94。但如果在移动之前没有保存 INLINECODE1014c49e（即 INLINECODEeabf782e），我们就永远找不到前半部分的剩余节点了。操作链表时，记住一句话：“想要动谁先备份谁”。
3. 循环终止条件
在合并链表的 INLINECODE0c070b56 循环中，条件是 INLINECODE472162a7。为什么不是 INLINECODE2e3c1707？因为对于奇数长度的链表（如示例1），前半部分会比反转后的后半部分多一个节点。当 INLINECODEd48de9f7（后半部分）用完时，first 所指的最后一个节点（原中点）自然就处于链表的末尾了，不需要再进行连接操作。
总结与进阶思考
通过这篇文章，我们不仅解决了“链表重排”这个问题，更重要的是，我们复习了链表操作的“三板斧”：快慢指针、反转链表、合并链表。这三个技术点在无数复杂的链表问题中都会反复出现。
当你下次面对一个复杂的链表问题时，试着问自己：
- 能不能通过快慢指针将链表一分为二？
- 是否需要反转其中一部分来改变顺序？
- 能否通过双指针或多指针交替操作来完成重构？
进阶挑战：
既然我们已经掌握了如何重排链表，你不妨思考一下：如果给定的是一个循环链表，或者是一个双向链表，解法会有什么不同？那将是更有趣的挑战。
希望这篇详细的解析能帮助你彻底拿下这个知识点。保持练习，代码会越来越优雅！