剑指 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)。
七、相关标签
- 链表