160. Intersection of Two Linked Lists

Loading...LeetCode

#0 暴力查表 O(n), O(n)
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        curA = headA
        curB = headB
        listB = []
        listA = []
        while curA is not None:
            listA.append((id(curA), curA.val))
            curA=curA.next
        
        while curB is not None:
            listB.append((id(curB), curB.val))
            curB = curB.next
        
        setA = set(listA)
        for tupleB in listB:
            if tupleB in setA:
                return ListNode(tupleB[1])
        
        return None

# 1
class Solution:
    # @param two ListNodes
    # @return the intersected ListNode
    def getIntersectionNode(self, headA, headB):
        if headA is None or headB is None:
            return None

        pa = headA # 2 pointers
        pb = headB

        while pa is not pb:
            # if either pointer hits the end, switch head and continue the second 
            # traversal, 
            # if not hit the end, just move on to next
            pa = headB if pa is None else pa.next
            pb = headA if pb is None else pb.next

        return pa # only 2 ways to get out of the loop, they meet or the both 
                  # hit the end=None

# the idea is if you switch head, the possible difference between length would be 
# countered. 
# On the second traversal, they either hit or miss. 
# if they meet, pa or pb would be the node we are looking for, 
# if they didn't meet, they will hit the end at the same iteration, pa == pb == None, 
# return either one of them is the same,None

# 2 把A的尾巴连到B如果有环就说明相交, 接着用快慢指针找入环点.
class Solution(object):
    def getIntersectionNode(self, A, B):
        if not A or not B: return None

        # Concatenate A and B
        last = A
        while last.next: last = last.next
        last.next = B

        # Find the start of the loop
        fast = slow = A
        while fast and fast.next:
            slow, fast = slow.next, fast.next.next
            if slow == fast:
                fast = A
                while fast != slow:
                    slow, fast = slow.next, fast.next
                last.next = None
                return slow

        # No loop found
        last.next = None
        return None