160.相交链表leetcode力扣算法题PYTHON_160.相交链表 python

题目描述：

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

图示两个链表在节点 c1 开始相交：

示例：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null

思路:

设两个指针，分别遍历A和B当遍历到A尾部时又从B开头开始，当遍历到B尾部时又从A开头开始。如果他们两个相交则他们会在交点相遇。如果他们两个不相交他们得交点则是none。

原理是：

设A的不公共部分长度是a，B的不公共长度是b，两者公共长度是c。

当A走过a又走过c时会从B的开头开始走，然后经过b到达交点这时候走过的总路程是a+c+b

当B走过b又走过c时会从A的开头开始走，然后经过a到达交点这时候走过的总路程是b+c+a

两者走过的路程相等而且在交点相遇

代码：

class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode):
        if not headA or not headB:
            return None
        nodeA = headA
        nodeB = headB
        while(nodeA !=nodeB):
            nodeA = nodeA.next if nodeA else headB
            nodeB = nodeB.next if nodeB else headA
        return nodeA