Skip to content

Instantly share code, notes, and snippets.

What would you like to do?
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# = 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
while and
s =
f =
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用同樣速度一起前進, 一定會走到一起.
s = f = head
is_cycle = False
while f and
s =
f =
if s == f:
is_cycle = True
if not is_cycle:
return None
s = head
while s!=f:
s =
f =
return s
def detectCycle(self, head: ListNode) -> ListNode:
visited = set([])
cur = head
while cur:
if cur in visited:
return cur
cur =
return None
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment