剑指offer52 两个链表的第一个公共节点【双指针】
题目描述
输入两个链表,找出它们的第一个公共节点。
如下面的两个链表:
在节点 c1 开始相交。
示例 1:
1 | 输入:intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 |
示例 2:
1 | 输入:intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 |
注意:
- 如果两个链表没有交点,返回
null
. - 在返回结果后,两个链表仍须保持原有的结构。
- 可假定整个链表结构中没有循环。
- 程序尽量满足 O(n) 时间复杂度,且仅用 O(1) 内存。
解题思路
方法一:模拟+双指针
先计算出两个链表的长度,让长的一方先走 两方的距离差,进而像快慢指针一样一起往前走,判断是否相等
代码实现
1 | public ListNode getIntersectionNode(ListNode headA, ListNode headB) { |
复杂度分析
时间复杂度:O(a+b)
空间复杂度:O(1)
方法二:模拟+双指针
两方在各自的链表上顺序遍历一步,遍历完自己后遍历对方的,直到找到共同节点或者为null。当走到对方上,走的步数是相同的(a+b)-c;c为共同结点的个数。
代码实现
1 | public class Solution { |
复杂度分析
时间复杂度:O(a+b)
空间复杂度:O(1)
资料
剑指offer52 两个链表的第一个公共节点【双指针】
You need to set
install_url
to use ShareThis. Please set it in _config.yml
.