前往此题

解题思路

题目中的相交指的是同时走到同一个节点上，可以通过拼接链表的方式来解决这个问题。

设链表A的前半部分为a，链表B的前半部分为b, 后半的相交部分为c。也就是说当链表A走在相交处的时候链表B也必定同时走在相交处。

算法过程

1. 同时遍历链表A，链表B
2. 链表A走完后就走链表B，链表B走完后就走链表A
3. 由于链表A走到a + c ， 链表B走到b + c的时候，链表B比链表A多走了一步，再把链表A指向链表B，链表B指向链表A，a + c + b = b + c + a，链表A与链表B必然会在某一点相交ha==hb
4. 一旦ha==hb，遍历结束返回相交点，这个点必然是它们相交的起始点。
5. 如果这两个链表不相交，那ha最终会指向null，hb也将指向null。 返回ha即可

代码

# 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:
        ha,hb = headA, headB
        while ha != hb:
            ha = ha.next if ha else headB
            hb = hb.next if hb else headA
        return ha

复杂度分析

• 时间复杂度: O(M+N)
• 空间复杂度: O(1)