C++实现LeetCode(143.链表重排序)

前言LeetCode 第 143 题「重排链表」Reorder List要求把链表L0 → L1 → … → Ln-1 → Ln原地重排为L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …。题目通常附加一条限制不能只修改节点的值必须真正改变节点的连接关系。这条限制决定了做法。如果允许改值可以把所有值收集到数组里按目标顺序写回节点简单直接但题目要的是指针操作必须把链表「拆开、反转、交错合并」。常见误解是直接用一个数组存节点指针再重连这虽然也改变了连接关系但额外用了 O(n) 空间题目进阶要求 O(1) 额外空间标准解法是「找中点、反转后半、合并两半」。另一个常见错误是找中点后忘记把前半的尾部next置空导致两半仍然相连反转后半时就会把前半也卷进去形成环最后死循环。本文按三步拆解并逐行说明指针顺序。一、把目标拆成三步目标序列可以看成两部分交错前半段L0, L1, L2, …从前往后。后半段Ln, Ln-1, Ln-2, …从后往前。重排就是把后半段反转然后与前半段一个隔一个地合并。于是任务分解为找到链表中点把链表切成两半。反转后半段。把两半交替合并。三步都是链表的基本操作但组合时边界很多节点数为奇数时前半比后半多一个节点数为偶数时两半等长只有一个节点时直接返回合并时不能丢掉任何一截。时间复杂度 O(n)找中点走一遍反转走一遍合并走一遍。空间复杂度 O(1)只用了几个指针。二、找中点与切分用快慢指针找中点slow每次走一步fast每次走两步。循环条件是fast-next ! nullptr fast-next-next ! nullptr。这个条件让slow最终停在「前半段的最后一个节点」n 为奇数例如 5 个节点slow停在下标 2中间节点前半是 0..2后半是 3..4。n 为偶数例如 4 个节点slow停在下标 1前半是 0..1后半是 2..3。无论奇偶后半段长度都不超过前半段这为后面的合并循环提供了便利。找到中点后先保存second slow-next再执行slow-next nullptr。这一步是切分必须做。若不切前半的尾节点仍然指向后半的头反转后半时会沿着这条边把前半也串进来合并时两半互相指向很快形成环程序可能陷入死循环或输出错乱。切分后前半以head开头、slow结尾后半以second开头。此时两条链表互不相连。三、反转后半与交替合并反转用三指针prev、cur、next。每次先保存cur-next再让cur-next prev然后推进prev和cur。循环结束时prev是反转后的头。这部分与普通链表反转完全相同注意不要先改cur-next再保存后继。合并时first指向前半当前节点second指向后半当前节点。每一轮保存firstNext first-next。保存secondNext second-next。first-next second;second-next firstNext;first firstNext;second secondNext;循环条件是second ! nullptr。因为后半不长于前半后半走完时前半要么刚好走完要么还剩最后一个节点这个节点已经在前一轮被second-next firstNext接上不需要额外处理。若循环条件写成first ! nullptr second ! nullptr当后半先空时也能退出但若前半先空理论上不会因为后半不长于前半就会解引用空指针。用second作为条件最稳。第 1、2 步的保存不能省。第 3 步会覆盖first-next第 4 步会覆盖second-next如果不提前保存下一轮就找不到两条链表的后续节点链表会被截断。四、完整实现// 适用于 C17#include iostreamstruct 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) {}};void reorderList(ListNode* head) {if (head nullptr || head-next nullptr) {return;}// 1. 快慢指针找中点slow 停在前半的最后一个节点ListNode* slow head;ListNode* fast head;while (fast-next ! nullptr fast-next-next ! nullptr) {slow slow-next;fast fast-next-next;}// 2. 切分并反转后半ListNode* second slow-next;slow-next nullptr;ListNode* prev nullptr;while (second ! nullptr) {ListNode* next second-next;second-next prev;prev second;second next;}second prev;// 3. 交替合并两半ListNode* first head;while (second ! nullptr) {ListNode* firstNext first-next;ListNode* secondNext second-next;first-next second;second-next firstNext;first firstNext;second secondNext;}}void printList(const ListNode* head) {for (const ListNode* p head; p ! nullptr; p p-next) {std::cout p-val ;}std::cout \n;}int main() {ListNode* head new ListNode(1);head-next new ListNode(2);head-next-next new ListNode(3);head-next-next-next new ListNode(4);head-next-next-next-next new ListNode(5);reorderList(head);printList(head); // 按定义应为 1 5 2 4 3while (head ! nullptr) {ListNode* next head-next;delete head;head next;}return 0;}以 1、2、3、4、5 为例slow停在中点 3前半是 1→2→3后半是 4→5反转后变成 5→4合并得到 1→5→2→4→3。若节点数是 4前半 1→2后半 3→4反转后 4→3合并得到 1→4→2→3也符合「首、尾、次首、次尾」的规律。main里手动new了五个节点最后逐个delete是为了演示完整的所有权LeetCode 的判题环境会统一回收不需要在函数里释放。真实工程中更推荐用std::unique_ptr管理节点或在reorderList之外用容器持有节点。常见坑点1. 只交换节点的值❌ 用数组收集值再按目标顺序写回val。✅ 题目要求改变连接关系按「找中点、反转、合并」操作指针。2. 忘记切断两半❌ 找到中点后直接反转slow-next开始的链表不置空slow-next。✅second slow-next; slow-next nullptr;再反转。3. 反转时先改指针再保存后继❌cur-next prev; next cur-next;next拿到的是prev。✅ 先next cur-next;再改指向。4. 合并时丢失后半的后续❌ 只保存firstNext不保存secondNextsecond-next被覆盖后找不到下一段。✅ 两个next都要在覆盖前保存。5. 合并循环条件写错❌while (first ! nullptr)前半走完后解引用空指针。✅while (second ! nullptr)后半不长于前半天然安全。6. 中点条件写成fast ! nullptr fast-next ! nullptr❌slow停在中间偏右后半长度可能大于前半合并时前半先空。✅ 用fast-next ! nullptr fast-next-next ! nullptr让slow停在前半末尾。7. 空表或单节点没处理❌ 直接进入找中点head-next为空时仍访问head-next-next。✅ 入口判断head nullptr || head-next nullptr直接返回。8. 认为必须新建节点❌ 为每个值new ListNode再拼接。✅ 原地改next空间 O(1)不新建节点。总结步骤操作关键点找中点快慢指针slow停在前半末尾切分slow-next nullptr必须断开防止成环反转后半三指针先存后继再改指向合并交替接链保存两个next时间O(n)三遍扫描空间O(1)只用指针边界空表、单节点直接返回链表重排序的解法可以背成三句话快慢指针找中点并切断反转后半交替合并。真正容易出错的是「切断」和「保存后继」这两个动作——它们不改变算法框架却决定了链表会不会成环、会不会丢节点。把这两处写对奇偶长度的差异就会被循环条件自然吸收。