更多题解，请关注公众号：程序员学长，让你进大厂不走弯路

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

问题描述

LeetCode 剑指 Offer 52. 两个链表的第一个公共节点

输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。

要求：空间复杂度是O(1)，时间复杂度是O(m+n)。

示例：

image-20211002201858775

分析问题

这个问题最直观的想法就是遍历链表headA，然后把headA中的所有每个节点都加入到集合中。然后再循环遍历链表headB，判断结点是否在集合中，如果在，则返回该结点，该结点就代表第一个公共结点。如果不在，继续遍历，直到结束。如果headB的所有结点都不在集合中，则表明不相交，直接返回null。

def getIntersectionNode(headA,headB):
    nodes=set()
    while headA:
        nodes.add(headA)
        headA=headA.next
    while headB:
        if nodes.__contains__(headB):
            return headB
        headB=headB.next
    return None

该算法的时间复杂度是O(m+n)，空间复杂度是O(n)。其中m和n分别是链表headA和headB的长度。

由于题目要求时间复杂度是O(m+n)，空间复杂度是O(1)。我们这里可以使用双指针法将空间复杂度降低到O(1)。我们分别用两个指针p1和p2分别指向headA和headB，然后同时移动指针p1和p2。当p1到达headA的末尾时，让p1指向headB，当p2到达headB的末尾时，让p2指向headA，这样，当它们相遇时，所指的节点就是第一个公共结点。

Tips:假设headA不相交的部分是a，headB不相交的部分是b，公共部分是c，那么headA的长度为a+c，headB的长度为b+c，当a等于b时，可以知道p1和p2指针同时到达第一个公共结点；当a不等于b时，在p1移动了a+b+c时，即p1走完headA，又在headB上走了b时，p2也走了a+b+c，即p2走完headB，然后又在headA上走了a，此时p1和p2正好相遇，且指向了第一个公共结点。

image-20211002220833060

def getIntersectionNode(headA,headB):
    p1 = headA
    p2 = headB

    while p1 != p2:
        if p1:
            p1=p1.next
        else:
            p1=headB
        if p2:
            p2=p2.next
        else:
            p2=headA
    return p1