企业官网建设流程全解析

前言

相交链表和反转链表是两道方向不同、但都依赖「指针重新接线」的基础题。前者问两个单链表是否共用某段后继，后者要求把整条链表的指向完全颠倒。放在一起讲，是因为它们共享同一套底层技能：知道什么时候要暂存next、知道循环结束时哪个指针是新的头、知道空链表和单结点这些边界怎么处理。

常见的误解有三个。第一，判断相交时比较结点的值，而不是结点地址——值相同的两个独立结点会被误判成公共结点。第二，反转链表时先把cur->next改成prev，再去读cur->next找下一个结点，结果读到的是已经改掉的值，链表断裂。第三，认为递归反转只是「写法不同」，忽略它的递归深度等于链表长度，长链表上可能栈溢出。

本文先讲相交链表的 Y 形结构和两种 O(1) 空间的做法，再讲反转链表的迭代三指针法与递归法，最后把完整代码、复杂度与边界放在一起核对。

一、相交链表

结构

两个单链表相交，指从某个结点开始，它们共用同一段后继。因为每个结点只有一个next，一旦共用某个结点，之后的所有结点必然完全相同，形状像字母 Y，不可能是 X 形。

由此得到两条性质：

1. 
   
2. 相交的两个无环链表，尾结点一定相同；
3. 
   
4. 从第一个公共结点到末尾，两条链表的长度相同。
5. 
   

设 A 的独立前缀长度为 a，B 的独立前缀长度为 b，公共后缀长度为 c。A 的总长是 a + c，B 是 b + c。若让较长的链表先走 |a - b| 步，两个指针到公共结点的剩余距离就相等，之后同步前进，第一次相等的位置就是答案。

方法一：长度差

先求两条链表的长度，算出差值，让长的先走差值步，再同步前进。

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

struct ListNode {
int val = 0;
ListNode* next = nullptr;
};

std::size_t listLength(const ListNode* head) {
std::size_t n = 0;
for (const ListNode* p = head; p != nullptr; p = p->next) {
++n;
}
return n;
}

ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
if (headA == nullptr || headB == nullptr) {
return nullptr;
}
const std::size_t lenA = listLength(headA);
const std::size_t lenB = listLength(headB);

ListNode* longer = headA;
ListNode* shorter = headB;
std::size_t diff = 0;
if (lenA >= lenB) {
diff = lenA - lenB;
} else {
longer = headB;
shorter = headA;
diff = lenB - lenA;
}
for (std::size_t i = 0; i < diff; ++i) {
longer = longer->next;
}
while (longer != shorter) {
longer = longer->next;
shorter = shorter->next;
}
return longer;
}

对齐之后两条链表的剩余长度相同，所以它们会同时变成空，或者同时到达公共结点。while (longer != shorter)不需要额外的空指针判断：不相交时两者最终都是空，循环结束时返回空，正好表示「没有公共结点」。对齐循环的次数严格小于较长链表的长度，不会在循环中走空。

方法二：双指针切换

两个指针分别从 A、B 出发，走到空就切换到另一条链表的头。若相交，它们会在第一个公共结点相遇；若不相交，会同时走到空。

// 适用于 C++17
ListNode* getIntersectionNodeTwoPointer(ListNode* headA, ListNode* headB) {
ListNode* a = headA;
ListNode* b = headB;
while (a != b) {
a = (a == nullptr) ? headB : a->next;
b = (b == nullptr) ? headA : b->next;
}
return a;
}

两个指针走过的总路程都是 m + n，速度相同，所以同时到达终点。切换相当于自动补齐了长度差，不需要先求长度。前提是链表无环；有环时指针永远走不到空，循环不会结束。

二、反转链表

迭代三指针法

维护三个指针：prev是已经反转部分的头，cur是当前待处理结点，next暂存cur的后继。每一轮做四件事：

1. 
   
2. 暂存next = cur->next；
3. 
   
4. 把cur->next指向prev；
5. 
   
6. prev前移到cur；
7. 
   
8. cur前移到next。
9. 
   

// 适用于 C++17
ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* cur = head;
while (cur != nullptr) {
ListNode* next = cur->next; // 必须先保存
cur->next = prev;
prev = cur;
cur = next;
}
return prev; // 原尾结点成为新头
}

顺序不能乱。如果先写cur->next = prev;再读cur->next找下一个，读到的是prev，原链表的后半段就丢了。暂存next是这段代码的核心。

循环结束时cur为空，prev指向原链表的最后一个结点，也就是反转后的头。返回prev，不是head——head现在是尾结点。

空链表时cur一开始就是空，循环不执行，返回prev（空），正确。单结点时循环走一轮，cur->next被设为空，prev指向该结点，返回它，正确。

递归法

递归的思路是：先反转head之后的子链表，得到新的头；再把head接到子链表尾部。

// 适用于 C++17
ListNode* reverseListRecursive(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head; // 空链表或单结点，已是反转结果
}
ListNode* newHead = reverseListRecursive(head->next);
head->next->next = head; // 让后继指回自己
head->next = nullptr; // 自己成为新的尾
return newHead;
}

递归返回后，head->next仍然指向原来的后继，而这个后继现在是反转后子链表的尾结点。让head->next->next = head，就把head接在了尾部；再把head->next置空，保证尾结点的next为空。顺序同样重要：必须先让后继指向head，再清空head->next，反过来就找不到那个后继了。

递归的深度等于链表长度，空间复杂度 O(n)。链表很长时（例如几十万结点），可能栈溢出。迭代法只用了三个指针，额外空间 O(1)，是更稳妥的选择。递归法的价值在于代码短、思路清晰，适合教学或深度可控的场景。

三、完整示例

下面把两道题的实现放在一个文件里，并给出一个构造相交链表的小工具，便于理解结构。

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

struct ListNode {
int val = 0;
ListNode* next = nullptr;
};

std::size_t listLength(const ListNode* head) {
std::size_t n = 0;
for (const ListNode* p = head; p != nullptr; p = p->next) {
++n;
}
return n;
}

ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {
if (headA == nullptr || headB == nullptr) {
return nullptr;
}
const std::size_t lenA = listLength(headA);
const std::size_t lenB = listLength(headB);

ListNode* longer = headA;
ListNode* shorter = headB;
std::size_t diff = 0;
if (lenA >= lenB) {
diff = lenA - lenB;
} else {
longer = headB;
shorter = headA;
diff = lenB - lenA;
}
for (std::size_t i = 0; i < diff; ++i) {
longer = longer->next;
}
while (longer != shorter) {
longer = longer->next;
shorter = shorter->next;
}
return longer;
}

ListNode* reverseList(ListNode* head) {
ListNode* prev = nullptr;
ListNode* cur = head;
while (cur != nullptr) {
ListNode* next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return prev;
}

int main() {
// 构造两条相交链表：
// A: 1 -> 2 -> 7 -> 8 -> 9
// B: 3 -> 7 -> 8 -> 9
ListNode n9{9, nullptr};
ListNode n8{8, &n9};
ListNode n7{7, &n8};
ListNode n2{2, &n7};
ListNode n1{1, &n2};
ListNode n3{3, &n7};

ListNode* common = getIntersectionNode(&n1, &n3);
std::cout << (common == &n7) << '\n'; // 按对齐逻辑应为 1

ListNode* reversed = reverseList(&n1);
std::cout << (reversed == &n9) << '\n'; // 原尾成为新头，应为 1

return 0;
}

这里用栈上的结点对象手工连线，没有new，所以不需要释放。n7同时被n2和n3指向，形成 Y 形；getIntersectionNode返回的应当是指向n7的指针。反转后原尾n9成为新头。这两个比较都是按代码逻辑推演的结果，不代表程序已经执行过。

四、复杂度与边界

边界情况要逐一确认：

• 
  
• 两条链表任一为空：不相交，返回空。
• 
  
• 两条链表是同一个头：第一个公共结点就是头本身，对齐差为 0，循环立即结束。
• 
  
• 两条链表等长但不相交：同步走到空，返回空。
• 
  
• 反转空链表：返回空。
• 
  
• 反转单结点：返回该结点，next已经是空。
• 
  
• 反转后原头变成尾，next必须为空，否则会成环。
• 
  

常见坑点

1. 相交比较值❌if (p->val == q->val) return p;—— 值相同不是同一结点。 ✅ 比较指针p == q。

2. 反转时先改指针再保存后继❌cur->next = prev; cur = cur->next;——cur走回prev，后半段丢失。 ✅ListNode* next = cur->next;放在最前面。

3. 反转后返回原头❌return head;—— 原头现在是尾结点。 ✅return prev;。

4. 递归反转忘记清空尾指针❌ 只写head->next->next = head;，没有head->next = nullptr;，链表成环。 ✅ 两行都写，顺序不能反。

5. 长度差用有符号减法❌int diff = lenA - lenB;为负时循环不执行，对齐错误。 ✅ 先比较大小，用大减小，差值保持非负。

6. 双指针切换用于有环链表❌ 不判环直接切换，环内永远走不到空。 ✅ 先判环；有环时单独处理入口。

7. 对齐循环越界❌ 对齐时无条件前进，超过较长链表长度后解引用空指针。 ✅ 循环次数严格等于长度差，差值小于较长链表长度。

8. 反转递归用于超长链表❌ 十万结点用递归反转，栈溢出。 ✅ 用迭代三指针，额外空间 O(1)。

总结

两道题都在考「指针改向的先后顺序」：相交题要先对齐再比较，反转题要先保存再改向。把next当作必须提前保存的易失数据，把「返回哪个指针」当作循环结束后的不变量来检查，绝大多数断链和成环问题都能避免。