面试题 02.07. 链表相交 ，python 题解疑问

[wangzhenzhou2020]

随想录 题解

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        """
        根据快慢法则，走的快的一定会追上走得慢的。
        在这道题里，有的链表短，他走完了就去走另一条链表，我们可以理解为走的快的指针。

        那么，只要其中一个链表走完了，就去走另一条链表的路。如果有交点，他们最终一定会在同一个
        位置相遇
        """
        cur_a, cur_b = headA, headB     # 用两个指针代替a和b

        
        while cur_a != cur_b:
            cur_a = cur_a.next if cur_a else headB      # 如果a走完了，那么就切换到b走
            cur_b = cur_b.next if cur_b else headA      # 同理，b走完了就切换到a
        
        return cur_a

疑问： 1 要是 a非空，b 为空。是不是错了 2 要是 a、b 无交点，岂不是死循环了？

[KinsoZHENG]

个人想法是： 在1,2的条件下，最终无论cur_a or cur_b都会到None, 届时 cur_a(None) == cur_b(None)条件成立 退出循环 则返回None, 符合题意

个人理解，如有误/理解不详细，请各位巨佬or卡哥指出，(督催我这个菜鸡学习)

[wangzhenzhou2020]

1 2 两种情况，“cur_a or cur_b都会到None”，你确定吗？我不理解。

[KinsoZHENG]

您可以再感受下 快慢法则 (题意里两个链表长度不相同)

或者将None节点也当成一个相交节点 可能会比较好理解？

长度不一致带来走的快/慢，快的会赶上慢的 即在None节点赶上/同时追上None节点

表达能力有限，请体谅

[wangzhenzhou2020]

我知道，如果两链表相交，自然有解。

但如果两个链表不相交，岂不是死循环了？

你的意思是不相交的链表，也不会死循环？

[KinsoZHENG]

“你的意思是不相交的链表，也不会死循环？”

是的，你可以理解为: 两个不相交的链表，因为快慢，最终在None节点相交

cur_a = cur_a.next if cur_a else headB # 如果a走完了，那么就切换到b走 cur_b = cur_b.next if cur_b else headA # 同理，b走完了就切换到a 代码中做判断的条件是: 当前节点是否存在值 (if cur_a else headB) [而不是下一节点是否为None] 当两个指针同时到达各链表的最后一节点时，next则都为None 进入下次循环时，进行条件判断 cur_a(None) == cur_b(None)，退出循环。而此时返回的结果则为None

不知道这样是否方便您理解

[wangzhenzhou2020]

懂了👌。谢谢。是我太浮躁了。感谢解答。

[KinsoZHENG]

不客气，一起进步~