1 题目
给你两个单链表的头节点 headA 和 headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null 。
图示两个链表在节点 c1 开始相交:
注意:
如果两个链表没有交点,返回 null。
在返回结果后,两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度,且仅用 O(1) 内存。
2 图解
考虑构建两个节点指针 A , B 分别指向两链表头节点 headA , headB ,做如下操作:
指针 A 先遍历完链表 headA ,再开始遍历链表 headB ,当走到 node 时,共走步数为:
a + (b - c)
a+(b−c)
指针 B 先遍历完链表 headB ,再开始遍历链表 headA ,当走到 node 时,共走步数为:
b + (a - c)
b+(a−c)
如下式所示,此时指针 A , B 重合,并有两种情况:
a + (b - c) = b + (a - c)
a+(b−c)=b+(a−c)
若两链表 有 公共尾部 (即 c > 0c>0 ) :指针 A , B 同时指向「第一个公共节点」node 。
若两链表 无 公共尾部 (即 c = 0c=0 ) :指针 A , B 同时指向 nullnull 。
因此返回 A 即可。
如下图所示,为 a = 5a=5 , b = 3b=3 , c = 2c=2 示例的算法执行过程。
(2)第二步
(3)第三步
(4)第四步
B走到了null,则指针接下来将会指向HeadA
(5)第五步
B指针指向HeadA
(6)第六步
A走到了null,则指针接下来将会指向HeadB
(7)第七步
(8)第八步
指针A等于指针B,此时返回指针A即可。如果两条链没有相交,一定会在Null相交,返回的是NULL
3 Python实现
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
'''
方法一:双指针法,图解参考https://leetcode.cn/problems/intersection-of-two-linked-lists/solution/intersection-of-two-linked-lists-shuang-zhi-zhen-l/
时间复杂度:O(m+n)O(m+n),其中 mm 和 nn 是分别是链表 \textit{headA}headA 和 \textit{headB}headB 的长度。两个指针同时遍历两个链表,每个指针遍历两个链表各一次。
空间复杂度:O(1)O(1)。
'''
A,B = headA,headB
while(A!=B):
A = A.next if A else headB
B = B.next if B else headA
return A
注意以上代码的用法
A if case else B表示如果case为真,则返回 A,否则返回 B。