关于leetcode:完虐算法两个链表的第一个公共结点

更多算法题解，请关注公众号《程序员学长》

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

问题形容

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

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

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

示例：

剖析问题

这个问题最直观的想法就是遍历链表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正好相遇，且指向了第一个公共结点。

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

更多算法题解，请关注公众号《程序员学长》