0143.重排链表
难度：🟡 中等
标签：链表、双指针、栈、递归
链接：143. 重排链表
题目描述
给定一个单链表 L 的头节点 head ，单链表 L 表示为： L₀ → L₁ → … → Lₙ₋₁ → Lₙ 请将其重新排列后变为： L₀ → Lₙ → L₁ → Lₙ₋₁ → L₂ → Lₙ₋₂ → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
示例 1：
输入: head = [1,2,3,4]
输出: [1,4,2,3]
示例 2：
输入: head = [1,2,3,4,5]
输出: [1,5,2,4,3]
解题思路
核心思想
本题的目标是对链表进行原地重排，将后半部分节点交错地插入到前半部分节点之间。这个问题可以优雅地分解为三个独立的、经典的链表操作子问题：
找到链表的中间节点。
反转链表的后半部分。
合并两个链表（前半部分和反转后的后半部分）。
思路选择
快慢指针 + 链表反转 + 链表合并 是解决此问题的标准最优思路，因为它可以在 O(1) 的额外空间内完成。
寻找中点：使用快慢指针法。快指针每次走两步，慢指针每次走一步。当快指针到达链表末尾时，慢指针正好位于链表的中点。
反转后半段：从中点将链表切断，然后对后半部分链表执行标准的反转操作。
合并链表：将前半部分链表和反转后的后半部分链表进行“拉链式”的交错合并。
关键步骤
找中点：初始化
slow和fast指针都指向head。fast每次走两步，slow每次走一步。当fast.next和fast.next.next为空时，slow就指向了中点或中点前的节点。分割与反转： a. 以
slow为界，将链表分割成前后两半。slow.next是后半段的头节点。 b. 将前半段的尾部断开，即slow.next = null。 c. 对后半段链表进行原地反转。交错合并： a. 初始化两个指针，
head1指向原链表的头，head2指向反转后后半段的头。 b. 在循环中，交错地将head2的节点插入到head1的节点之后。需要临时变量来保存各自的下一个节点，以防链表断裂。
代码实现
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @return {void} Do not return anything, modify head in-place instead.
*/
var reorderList = function (head) {
let slow = head, fast = head;
// 1. 快慢指针找中点，正确
while (fast.next !== null && fast.next.next !== null) {
fast = fast.next.next;
slow = slow.next;
}
// 2. 反转后半部分
let prev = null, cur = slow.next;
slow.next = null; // 断开链表
while (cur !== null) {
let temp = cur.next;
cur.next = prev;
prev = cur;
cur = temp;
}
// 3. 合并前后两半，逻辑清晰
// head 指向第一部分头，prev 指向第二部分头
while (head !== null && prev !== null) {
let temp1 = head.next;
let temp2 = prev.next;
head.next = prev;
prev.next = temp1;
head = temp1;
prev = temp2;
}
};
优点：此实现堪称模板，正确地分解问题并实现了每一步，时空效率都很高。
代码风格: 变量命名清晰，逻辑分支明确，是一个优秀的实现。
复杂度分析
时间复杂度：O(n) 其中 n 是链表的节点数。找中点、反转、合并三个步骤都是线性时间复杂度。
空间复杂度：O(1) 我们是在原链表上进行操作，只使用了常数个额外变量作为指针，空间消耗是恒定的。
相关题目
总结
本题是链表操作的集大成者，它将几个最基础、最重要的链表操作（找中点、反转、合并）串联起来，形成了一个更复杂的算法。熟练掌握这三个子问题的解法，是解决各类复杂链表问题的关键。