题目：

链接：LeetCode 143. 重排链表
难度：中等

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L₀ → L₁ → … → L_n-1 → L_n

请将其重新排列后变为：

L₀ → L_n → L₁ → L_n-1 → L₂ → L_n-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⁴]
• 1 <= node.val <= 1000

解题思路：

折半拆分 + 反转链表 + 合并链表。

1. 快慢指针找到链表的中间点，将其拆分成两半。
2. 反转后半个链表。
3. 将前半个链表和反转后的后半个链表合并。

代码：

/*** 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 reverseList(ListNode*& head) {  // 反转链表if (head->next == nullptr) return;ListNode* p = head;ListNode* q = head->next;p->next = nullptr;ListNode* t;while (q != nullptr) {t = q->next;q->next = p;p = q;q = t;}head = p;}void mergeList(ListNode* L1, ListNode* L2) {  // 合并链表ListNode* head = L1;ListNode* p;while (L2 != nullptr) {p = L1->next;L1->next = L2;L1 = p;p = L2->next;L2->next = L1;L2 = p;}}void reorderList(ListNode* head) {if (head->next == nullptr) return;ListNode* L1 = head;ListNode* L2 = head;while (L2->next != nullptr && L2->next->next != nullptr) {  // 快慢指针找中间节点L2 = L2->next->next;L1 = L1->next;}L2 = L1->next;L1->next = nullptr;L1 = head;reverseList(L2);mergeList(L1, L2);}
};

时间复杂度O(N)，空间复杂度O(1)。N为链表长度。