Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
leetcode-ll
# 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment