题目

输入两个链表，找出它们的第一个公共节点。

如下面的两个链表：

在节点 c1 开始相交。

分析

思路和算法

使用双指针的方法，可以将空间复杂度降至 O(1)O(1)。

若headA 和 headB其中之一为空，则不相交，返回None;

若均不为空，设两个新指针pA,pB分别指向 headA和headB，同时移动pA，pB。若pA/pB不为空，均移动到各自的下一个节点，否则pA指向headB，pB指向headA，直到pA 和pB指向同一个节点。

论证

求headA 的长度为m, headB的长度为n，对与相交链表headA/headB 将其分别分成两段，即：

m = a + c;? n = b + c (c 为headA 和 headB相交的公共部分)

因此在pA 和pB 相遇前，pA走过节点数为 m + b 即 a + c + b；pB 走过的节点数为 n + a，即 b + c + a。

因此pA 和 pB 走过的节点数相同，即相遇。

代码

# 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:
        if headA == None or headB == None:
            return None
        pA = headA
        pB = headB
        while pA != pB:
            pA = pA.next if pA else headB
            pB = pB.next if pB else headA
        return pA

=========================================================================

有缘人终会相遇！！！