【Leetcode刷题Python】106.相交链表

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 示例的算法执行过程。

思路来源链接：https://leetcode.cn/problems/intersection-of-two-linked-lists/solution/intersection-of-two-linked-lists-shuang-zhi-zhen-l/
（1）第一步

（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。