blob: 523ecd959dafc3c6ba2f32f0c72aa7c39af7e44b (
plain) (
blame)
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
|
def contains_cycle(node):
"""
Return True if the linked-list, `node`, contains a cycle.
"""
if not node:
return False
a = node
b = node.next
while a != b:
a = a.next
if b and b.next and b.next.next:
b = b.next.next
else:
return False
return True
################################################################################
# Bonus
################################################################################
def first_node_in_cycle(node):
"""
Given that the linked-list, `node`, contains a cycle, return the first
element of that cycle.
"""
# enter the cycle
a = node
b = node.next
while a != b:
a = a.next
b = b.next.next
# get the length of the cycle
beg = a
a = a.next
n = 1
while a != beg:
a = a.next
n += 1
# run b n-steps ahead of a
a = node
b = node
for _ in range(n):
b = b.next
# where they intersect is the answer
while a != b:
a = a.next
b = b.next
return a
################################################################################
# Tests
################################################################################
class Node(object):
def __init__(self, value, next=None):
self.value = value
self.next = next
def __repr__(self):
return "Node({}) -> ...".format(self.value)
d = Node('d')
c = Node('c', d)
b = Node('b', c)
a = Node('a', b)
d.next = b
print(first_node_in_cycle(a))
|
