剑指 Offer 52.两个链表的第一个公共节点
大家好，我是程序员吴师兄，欢迎来到 图解剑指 Offer 结构化专栏，在这个专栏里我将和大家一起学习如何用结构化的思维来思考、解题、写代码，希望能帮助你即使在面试的时候紧张也能做对。
AlgoMooc 算法慕课网，每道题目都有动画和图片，致力于帮助每个程序员通过算法面试！
今天分享的题目来源于 LeetCode 上的剑指 Offer 系列 面试题 52.两个链表的第一个公共节点。
题目汇总链接：https://www.algomooc.com/jianzhioffer
一、题目描述
输入两个链表，找出它们的第一个公共节点。
如下面的两个链表：
在节点 c1 开始相交。
注意：
- 如果两个链表没有交点，返回 null。
- 在返回结果后，两个链表仍须保持原有的结构。
- 可假定整个链表结构中没有循环。
- 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
二、题目解析
我们依旧用 四步分析法 进行结构化的分析。
- 模拟：模拟题目的运行。
- 规律：尝试总结出题目的一般规律和特点。
- 匹配：找到符合这些特点的数据结构与算法。
- 边界：考虑特殊情况。
1、模拟
首先假设 A 、B 两个链表是有相交节点的情况。
再假设 A 、B 两个链表是没有相交节点的情况。
2、规律
也就是说，无论 A、B 两个链表是否有相交点，最终都会指向一个相同的节点，要么是它们的公共尾部，要么是 NULL。
让指针 PA 和 pB 分别指向链表 A 和链表 B 的头结点，之后两个指针分别以步幅为 1 的速度向链表的尾部遍历。
- 当指针
pA遍历到链表 A 的尾节点时，此时指针pA走了 a 个节点，将指针pA指向链表 B 的头部，继续向后遍历，直至走到c1，此时指针PA总共走了a + ( b - c )步。 - 当指针
pB遍历到链表 B 的尾节点时，此时指针pB走了 b 个节点，将指针pB指向链表 A 的头部，继续向后遍历，直至走到c1，此时指针PB总共走了b + ( a - c )步。
根据数学知识，a + ( b - c ) = b + ( a - c ) ，如果 c > 0，表明两链表有公共尾部， c1 存在，两两链表同时到达 c1；如果 c = 0，表明两链表没有公共尾部，指针 PA 和 pB 都指向 NULL。
3、匹配
无。
4、边界
- A 链表为 null
- B 链表为 null
三、动画描述
隐藏内容
此处内容需要权限查看
会员免费查看四、图片描述
五、参考代码
// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// 边界判断
if (headA == null || headB == null) return null;
// 从两个链表的头结点开始遍历
ListNode pA = headA, pB = headB;
//指针 PA 和 指针 PB 不断向后遍历，直到找到相交点
//如果两个链表不相交，则相当于 null 是它们的相交点，因此不会跳不出 while 循环
while (pA != pB) {
// 指针 PA 一开始在链表 A 上遍历，当走到链表 A 的尾部即 null 时，跳转到链表 B 上
pA = pA == null ? headB : pA.next;
// 指针 PB 一开始在链表 B 上遍历，当走到链表 B 的尾部即 null 时，跳转到链表 A 上
pB = pB == null ? headA : pB.next;
}
return pA;
}
}
六、复杂度分析
时间复杂度
时间复杂度为 O( a + b)。
空间复杂度
空间复杂度为 O(1)。
七、相关标签
- 链表
