-
Notifications
You must be signed in to change notification settings - Fork 0
/
linked list cycle.py
82 lines (80 loc) · 2.37 KB
/
linked list cycle.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
'''
Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
'''
'''
Method 1: use hashtable O(n) time O(n) space
put every explored node into it, if current node exists in hashtable, return True
'''
class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
explored = {}
cur = head
while cur:
if cur not in explored: # different nodes may have same value
explored[cur] = cur.val
else:
return True
cur = cur.next # need to update the node
return False
'''
Method 2: slow fast pointers
slow pointer moves 1 node forward each time, fast moves 2, if they meet with each other, return True
'''
class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
'''
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Note: Do not modify the linked list.
Follow up:
Can you solve it without using extra space?
'''
'''
Method 1: for each explored node, point it to itself, if cur.next.next == cur.next, we found it(cur.next)
'''
'''
Method 2: slow fast pointers
1) find the 1st node they meet
2) slow start from begining, fast from meet node, forward with same spd, and the node they meet will be the start node
assume non loop contains m nodes, loop contains n nodes, when they 1st meet, slow moves m + x nodes, then 2(m+x) = m + x + an, hence
m + x = an, if fast moves an - x nodes with same spd as slow, it will reach the start node
'''
class Solution(object):
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
slow = head
fast = head
meet = None
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
meet = slow
break
if not meet:
return None
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow