160 Intersection of Two Linked Lists

题目

Intersection of Two Linked Lists

题解

由下图可以看出，如果两个链表相交的话，在相交节点以及之后的那一部分必然是相同的，而相交节点就是第一个同时位于链表A与链表B的节点。

graph LR
    A1 --> A2 --> C1 --> C2 --> C3
    B1--> B2 --> B3 --> C1
    style C1 fill:red

由于链表A与链表B不一定有相同长度，所以同时遍历两个链表不一定会同时抵达相交节点，但是我们可以运用下面的技巧来解决这个问题：节点1先遍历链表A再遍历链表B，节点2先遍历链表B再遍历链表A，这样节点1与节点2必然会在相交节点上相遇。证明如下：假设链表A的头部到相交节点的距离为a，而链表B的头部到相交节点的距离为b，相交部分的长度为c，因为 \(a + c + b = b + c + a\)，所以节点1与节点2必然在相交节点上相遇。

代码

class Solution:
    def getIntersectionNode(
        self, headA: ListNode, headB: ListNode
    ) -> Optional[ListNode]:
        nodeA = headA
        nodeB = headB
        while nodeA is not nodeB:
            if nodeA is None:
                nodeA = headB
            else:
                nodeA = nodeA.next

            if nodeB is None:
                nodeB = headA
            else:
                nodeB = nodeB.next

        return nodeA