两个链表的第一个公共结点

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

图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

自定义评测：

评测系统 的输入如下（你设计的程序 不适用 此输入）：

intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
listA - 第一个链表
listB - 第二个链表
skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案 。

---

直观解法

先计算长度，然后长链表先走，最后一起走

# 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 = 0
        b = 0
        p = headA
        q = headB
        # 先计算各自长度
        while p:
            p = p.next
            a += 1

        while q:
            q = q.next
            b += 1
        
        p = headA
        q = headB
        print('a,b', a, b)
        c = a - b
        if c > 0:
            p = headA
            q = headB
        else:
            p = headB
            q = headA
            c = -c

        # 长链表先走，然后一起走 
        while c:
            if not p or not q:
                return None
            p = p.next
            c = c - 1
        while p and q:
            if p == q:
                return p
            p = p.next
            q = q.next
        return 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_dict = dict()
        while headA:
            a_dict[headA] = 1
            headA = headA.next
        
        while headB:
            if headB in a_dict:
                return headB
            else:
                headB = headB.next
        return 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:
        pA = headA
        pB = headB
        while pA != pB:
            if not pA:
                pA = headB
            else:
                pA = pA.next
            if not pB:
                pB = headA
            else:
                pB = pB.next
        return pA