题目描述

blablabla

样例

blablabla

算法1

(hashmap法) $O(n^2)$

blablabla

时间复杂度分析：blablabla

P 代码

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def findFirstCommonNode(self, headA, headB):
        """
        :type headA, headB: ListNode
        :rtype: ListNode
        """
        if not headA or not headB:
            return None
        memo1 = set()
        memo2 = set()
        while headA.next or headB.next:
            if headA not in memo1:
                memo1.add(headA)
            if headB not in memo2:
                memo2.add(headB)
            if headA in memo2:
                return headA
            if headB in memo1:
                return headB
            if headA.next:
                headA = headA.next
            if headB.next:
                headB = headB.next
        return None

算法2

(长的先走短的跟上法) $O(n^2)$

blablabla

时间复杂度分析：blablabla

P 代码

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def findFirstCommonNode(self, headA, headB):
        """
        :type headA, headB: ListNode
        :rtype: ListNode
        """
        if not headA or not headB:
            return None
        la, lb = 0, 0
        rootA, rootB = headA, headB
        while rootA.next:
            la += 1
            rootA = rootA.next
        while rootB.next:
            lb += 1
            rootB = rootB.next
        if la < lb:
            la, lb = lb, la
            headA, headB = headB, headA
        while la - lb and headA.next:
            headA = headA.next
            la -= 1

        while headA.next:
            if headA == headB:
                return headA
            headA = headA.next
            headB = headB.next
        return None

算法3

(循环追赶法) $O(n^2)$

blablabla

时间复杂度分析：blablabla

P 代码

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def findFirstCommonNode(self, headA, headB):
        """
        :type headA, headB: ListNode
        :rtype: ListNode
        """
        if not headA or not headB:
            return None
        rootA, rootB = headA, headB
        while rootA != rootB:
            if rootA:
                rootA = rootA.next
            else:
                rootA = headB # 这里
            if rootB:
                rootB = rootB.next
            else:
                rootB = headA # 这里

        return rootA

此方法借鉴自邓泽军同学