交叉链表求交点（关键词：链表/交叉链表/交点/交集）

交叉链表求交点

实现

def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        if headA is not None and headB is not None:
            pa, pb = headA, headB
            
            while pa is not pb:
                pa = pa.next if pa is not None else headB
                pb = pb.next if pb is not None else headA
            
            return pa

关于代码的一点解释

pa、pb 2 个指针的初始位置是 headA、headB 头结点，pa、pb 两个指针一直往后遍历。
直到 pa 指针走到链表的末尾，然后 pa 指向 headB；
直到 pb 指针走到链表的末尾，然后 pb 指向 headA；
然后 pa、pb 再继续遍历；
每次 pa、pb 指向 None，则将 pa、pb 分别指向 headB、headA。
循环的次数越多，pa、pb 的距离越接近，直到 pa 等于 pb。

参考文献

1. 160. Intersection of Two Linked Lists - LeetCode；
2. https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/49846/Python-solution-for-intersection-of-two-singly-linked-lists；
3. https://leetcode.com/problems/intersection-of-two-linked-lists/discuss/49798/Concise-python-code-with-comments；
4. https://leetcode.com/submissions/detail/194298767/。

最后

以上就是心灵美柜子为你收集整理的交叉链表求交点（关键词：链表/交叉链表/交点/交集）的全部内容，希望文章能够帮你解决交叉链表求交点（关键词：链表/交叉链表/交点/交集）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。