leetcode-ll

160. Intersection of Two Linked Lists.py

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

class Solution:
    """
    PC:
        - no cycle return None
    S:O(1) --> 自己走完, 接到另一條的頭, 如果有cycle總有一天會走到一起， 走到一起的node就是intersection
    s:O(n) --> 用hashmap, 把第一條走完存起來, 注意是去存node itself 而不是node.val. 在traverse第二條如果current node在visited return node.
    
    """
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        m = headA
        n = headB
        while m != n:
            if m:
                m = m.next
            else:
                #走完接到別人那邊
                m = headB
            if n:
                n = n.next
            else:
                #
                n = headA
        return m
    
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        visited = set([])
        m = headA
        while m:
            visited.add(m)
            m = m.next
        n = headB
        while n:
            if n in visited:
                return n
            n = n.next
        
        return None