企业官网建设流程全解析

前言

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, …从后往前。
• 
  

重排就是把后半段反转，然后与前半段一个隔一个地合并。于是任务分解为：

1. 
   
2. 找到链表中点，把链表切成两半。
3. 
   
4. 反转后半段。
5. 
   
6. 把两半交替合并。
7. 
   

三步都是链表的基本操作，但组合时边界很多：节点数为奇数时前半比后半多一个；节点数为偶数时两半等长；只有一个节点时直接返回；合并时不能丢掉任何一截。

时间复杂度 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指向后半当前节点。每一轮：

1. 
   
2. 保存firstNext = first->next。
3. 
   
4. 保存secondNext = second->next。
5. 
   
6. first->next = second;
7. 
   
8. second->next = firstNext;
9. 
   
10. first = firstNext;
11. 
    
12. second = secondNext;
13. 
    

循环条件是second != nullptr。因为后半不长于前半，后半走完时前半要么刚好走完，要么还剩最后一个节点；这个节点已经在前一轮被second->next = firstNext接上，不需要额外处理。若循环条件写成first != nullptr && second != nullptr，当后半先空时也能退出，但若前半先空（理论上不会，因为后半不长于前半），就会解引用空指针。用second作为条件最稳。

第 1、2 步的保存不能省。第 3 步会覆盖first->next，第 4 步会覆盖second->next；如果不提前保存，下一轮就找不到两条链表的后续节点，链表会被截断。

四、完整实现

// 适用于 C++17
#include <iostream>

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) {}
};

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 3

while (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，不保存secondNext，second->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)，不新建节点。

总结

链表重排序的解法可以背成三句话：快慢指针找中点并切断，反转后半，交替合并。真正容易出错的是「切断」和「保存后继」这两个动作——它们不改变算法框架，却决定了链表会不会成环、会不会丢节点。把这两处写对，奇偶长度的差异就会被循环条件自然吸收。