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:
"""
Thought Process:
We use hashmap to store node we visted already, if current node in the hashmap, it mean there's cycle and it's first node starting a cycle.
If there is no cycle, return None
s=f=head
while f.next and f.next.next:
s = s.next
f = f.next.next
if s==f:
return s
Similar to 287. Find the Duplicate Number (In array)
"""
def detectCycle(self, head: ListNode) -> ListNode:
"""
floyd's algorithm
step1:先找有沒有cycle用slow and faster two pointers, 找到cycle retur None 且記得終止迴圈
step2:找到cycle把slow, 再指回head, 然後slow and fast用同樣速度一起前進, 一定會走到一起.
T:O(n)
S:O(1)
"""
s = f = head
is_cycle = False
while f and f.next:
s = s.next
f = f.next.next
if s == f:
is_cycle = True
#有cycle要記得打斷迴圈不然會TLE跳不出來迴圈
break
if not is_cycle:
return None
s = head
while s!=f:
s = s.next
f = f.next
return s
def detectCycle(self, head: ListNode) -> ListNode:
visited = set([])
cur = head
while cur:
if cur in visited:
return cur
visited.add(cur)
cur = cur.next
return None
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment