链表相交

题目

思路

设相交部分长度为c，链表A的长度为A，链表B的长度为B。
AD距离为a，BD距离为b。
A - a = B - b
转换后得，A + b = B + a。意味着如果链表相交，那么 遍历完A链表长度再走一段距离b 一定会相等于 遍历完B链表再走一段距离a。
如果不相交，A + B = B + A，最终共同指向None。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        a, b = headA, headB
        while a != b:
            a = a.next if a else headB
            b = b.next if b else headA
        return a