160. 相交链表 - 题解与详细分析

题目描述

给你两个单链表的头节点 headA 和 headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null。

图示两个链表在节点 c1 开始相交：

text

A: a1 → a2 ↘ c1 → c2 → c3 ↗ B: b1 → b2 → b3

注意：

• 题目数据保证整个链式结构中不存在环
• 函数返回结果后，链表必须保持其原始结构

解题思路

这道题要求找到两个链表的相交节点。由于链表可能长度不同，但相交后的部分长度相同，我们可以通过以下方法解决：

核心思想

1. 计算链表长度：分别遍历两个链表，得到它们的长度
2. 对齐起点：让长链表先移动长度差值的步数，使两个链表的剩余长度相等
3. 同时遍历：两个指针同时移动，比较节点是否相同

为什么这样有效？

• 如果两个链表相交，那么从相交点到链表末尾的长度是相同的
• 通过让长链表先走差值步，两个指针会同时到达相交点（如果存在）

代码实现

c

/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode *cur1 = headA; struct ListNode *cur2 = headB; int a = 0; int b = 0; // 计算链表A的长度 while(cur1) { a++; cur1 = cur1->next; } // 计算链表B的长度 while(cur2) { b++; cur2 = cur2->next; } // 重置指针到链表头部 cur1 = headA; cur2 = headB; int c = 0; // 让长链表先移动长度差值的步数 if(a > b) { c = a - b; while(c--) { cur1 = cur1->next; } } else { c = b - a; while(c--) { cur2 = cur2->next; } } // 同时遍历两个链表，寻找相交节点 while(cur1) { if(cur1 == cur2) { return cur1; } cur1 = cur1->next; cur2 = cur2->next; } return NULL; }

代码详解

第一部分：计算链表长度

c

struct ListNode *cur1 = headA; struct ListNode *cur2 = headB; int a = 0; int b = 0; // 计算链表A的长度 while(cur1) { a++; cur1 = cur1->next; } // 计算链表B的长度 while(cur2) { b++; cur2 = cur2->next; }

• 使用两个指针分别遍历两个链表
• 计数器 a 和 b 分别记录链表A和链表B的长度

第二部分：对齐起点

c

cur1 = headA; cur2 = headB; int c = 0; if(a > b) { c = a - b; while(c--) { cur1 = cur1->next; } } else { c = b - a; while(c--) { cur2 = cur2->next; } }

• 重置指针到链表头部
• 计算长度差值 c
• 让长链表的指针先移动 c 步，使两个指针后的剩余长度相等

第三部分：寻找相交节点

c

while(cur1) { if(cur1 == cur2) { return cur1; } cur1 = cur1->next; cur2 = cur2->next; } return NULL;

• 两个指针同时移动
• 比较节点地址是否相同（注意：是比较节点本身，不是节点值）
• 找到相同节点则返回，否则返回 NULL

执行过程可视化

以题目示例为例：

text

链表A: a1 → a2 → c1 → c2 → c3 链表B: b1 → b2 → b3 → c1 → c2 → c3

执行步骤：

1. 计算长度：
   • 链表A长度：5
   • 链表B长度：6
2. 对齐起点：
   • 长度差：1
   • 链表B指针先移动1步：b2 → b3 → c1 → c2 → c3
3. 同时遍历：
   • A: a1 → a2 → c1 → c2 → c3
   • B: b2 → b3 → c1 → c2 → c3
   • 在节点c1处相遇，返回c1

优化方案：双指针法

还有一种更巧妙的方法，不需要计算链表长度：

c

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { if (headA == NULL || headB == NULL) return NULL; struct ListNode *pA = headA; struct ListNode *pB = headB; while (pA != pB) { pA = pA == NULL ? headB : pA->next; pB = pB == NULL ? headA : pB->next; } return pA; }

原理：

• 两个指针分别遍历两个链表
• 当指针到达链表末尾时，切换到另一个链表的头部
• 如果两个链表相交，指针会在相交点相遇
• 如果不相交，指针会同时到达NULL

复杂度分析

长度差法

• 时间复杂度：O(m+n)，其中m和n分别是两个链表的长度
• 空间复杂度：O(1)，只使用常数级别的额外空间

双指针法

• 时间复杂度：O(m+n)
• 空间复杂度：O(1)

关键点总结

1. 比较节点地址：注意是比较节点本身（指针地址），不是节点值
2. 链表无环：题目保证链表无环，简化了问题
3. 保持原始结构：算法不应该修改链表结构
4. 边界情况：处理空链表的情况

测试用例考虑

1. 不相交的链表：返回NULL
2. 完全相同的链表：返回头节点
3. 一个链表是另一个的子集：返回较长链表的头部
4. 在中间节点相交：返回相交节点
5. 空链表：返回NULL

应用场景

这种链表相交问题在实际开发中有多种应用：

1. 内存管理：检测两个数据结构是否共享内存区域
2. 图算法：在树或图中寻找公共节点
3. 版本控制系统：寻找代码分支的合并点
4. 数据库查询：优化连接查询的执行计划

总结

寻找相交链表节点是一个经典的链表问题，掌握两种解法都很重要：

1. 长度差法：思路直观，容易理解和实现
2. 双指针法：代码简洁，不需要计算长度

关键技巧：

• 利用相交后部分长度相同的特性
• 通过对齐起点来简化比较过程
• 注意指针操作和边界条件处理

这道题考察了对链表结构的理解和双指针技巧的应用，是面试中常见的问题之一。