乐趣区

关于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

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

退出移动版