C++实现相交链表与反转链表算法详解
发布时间：2026-10-16 |
4人浏览过
针对C++开发者在处理链表数据结构时遇到的常见问题，本文深入解析两个经典算法：如何高效定位两条单链表的起始相交节点，以及如何使用迭代和递归两种方式原地反转单链表。内容包含完整的可运行代码、逻辑图解说明及易错点分析。
查找单链表相交的起始节点
给定两个单链表的头节点 headA 和 headB，目标是找出它们相交的起始节点。如果两个链表没有交点，则返回 nullptr。需要明确的是，这里的“相交”指的是指针地址相同（即内存中的同一个节点），而非仅仅是节点存储的数值相等。
思路解析
解决此问题的关键在于利用链表尾部对齐的特性。假设两个链表在相遇前分别有不同的长度，如果我们将较长的链表向前移动，直到剩余长度与短链表一致，那么两个链表尾部的长度就完全相同了。此时，两个指针同步向后遍历，首次相遇的位置即为相交起始点。
具体步骤如下：
- 遍历两个链表，分别计算它们的总长度
lenA和lenB。 - 定义两个指针
curA和curB重新指向各自链表的头部。 - 比较长度，若
lenA大于lenB，让curA先向后移动lenA - lenB步；反之则让curB移动。这一步确保了两个指针距离链表尾部的距离相等。 - 两个指针同时向后移动，每次一步。当
curA == curB时，返回该节点；若遍历结束仍未相遇，则返回nullptr。
经过上述长度差的调整，两个指针进入了相同的“相对位置”状态，如图示，此时同步推进即可精准定位交点。
C++ 代码实现
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode* curA = headA;
ListNode* curB = headB;
int lenA = 0;
int lenB = 0;
// 1. 计算链表A的长度
while(curA != nullptr){
lenA++;
curA = curA->next;
}
// 2. 计算链表B的长度
while(curB != nullptr){
lenB++;
curB = curB->next;
}
// 重置指针至头节点
curA = headA;
curB = headB;
// 3. 确保 curA 指向较长的链表，方便后续统一处理
if(lenA < lenB){
swap(lenA, lenB);
swap(curA, curB);
}
// 4. 计算长度差值，并移动长链表指针
int gap = lenA - lenB;
while(gap){
gap--;
curA = curA->next;
}
// 5. 同步遍历，寻找交点
while(lenB){
if(curA == curB)
return curA; // 直接返回节点指针
curA = curA->next;
curB = curB->next;
lenB--;
}
return nullptr; // 无交点
}
};
反转单链表
给定单链表的头节点 head，要求将其反转并返回新的头节点。例如，输入 [1,2,3,4,5]，输出应为 [5,4,3,2,1]。
迭代法（双指针/三指针）
迭代法是空间复杂度最优解（O(1)），核心思想是通过三个指针动态修改节点的 next 指向，使其指向前一个节点。
操作步骤：
- 判空：如果链表为空，直接返回
nullptr。 - 初始化指针：
cur指向当前正在处理的节点，初始为head。per(previous) 指向前一个节点，初始为nullptr（因为新头节点的 next 将是 null）。temp作为临时变量，用于保存cur的下一个节点，防止断链后无法继续遍历。
- 循环遍历：当
cur不为空时：- 用
temp保存cur->next。 - 将
cur->next指向per，完成局部反转。 per前进一步，移动到cur的位置。cur前进一步，移动到temp的位置。
- 用
- 返回结果：循环结束时，
cur为null，per指向原链表的最后一个节点，即新链表的头节点，返回per。
/**
* 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:
ListNode* reverseList(ListNode* head) {
if(head == nullptr) // 处理空链表情况
return nullptr;
ListNode* per = nullptr; // 前驱节点，初始为空
ListNode* cur = head; // 当前节点
ListNode* temp; // 临时节点
while(cur){ // 当当前节点不为空时执行
temp = cur->next; // 1. 暂存下一个节点，防止断链
cur->next = per; // 2. 核心反转：当前节点指向前驱
per = cur; // 3. 前驱指针右移
cur = temp; // 4. 当前指针右移
}
return per; // 返回新的头节点
}
};
递归法
递归法利用系统栈隐式维护路径，代码更简洁，但空间复杂度为 O(N)。主要思路是递归到链表末尾，然后在回溯过程中修改指向。
为了便于理解，可以封装一个内部递归函数 reverse(per, cur)：
- 终止条件：当
cur为null时，说明已经处理完了所有节点，返回此时的per（即新的头节点）。 - 递归过程：
- 保存cur的下一个节点到temp。 - 反转当前指向：让cur->next指向per。 - 递归调用：以cur为新的前驱，temp为新的当前节点进行下一步。
/**
* 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 {
private:
// 辅助递归函数
ListNode* reverse(ListNode* per, ListNode* cur) {
if(cur == nullptr) // 到达原链表尾部
return per;
ListNode* temp = cur->next; // 保存后继
cur->next = per; // 反转指向
return reverse(cur, temp); // 递归处理下一段
}
public:
ListNode* reverseList(ListNode* head) {
if(head == nullptr)
return nullptr;
return reverse(NULL, head); // 初始前驱为空，当前为头节点
}
};
以上就是C++实现相交链表检测与反转链表的详细内容，更多关于C++链表算法优化的资料请关注本站其它相关文章！
本站声明
本文内容仅供参考，不代表本站观点。转载或引用请注明出处。如发现内容问题，请通过联系我们页面反馈。
