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

2次阅读

共计 1034 个字符，预计需要花费 3 分钟才能阅读完成。

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

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

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

正文完