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
83
84
85
86
87
88
|
import unittest
################################################################################
# Solution
################################################################################
def contains_cycle(x):
if not x:
return False
elif not x.next:
return False
a = x
b = x.next
while b.next:
if a == b:
return True
a = a.next
b = b.next.next
return False
################################################################################
# Tests
################################################################################
class Test(unittest.TestCase):
class LinkedListNode(object):
def __init__(self, value, next=None):
self.value = value
self.next = next
def test_linked_list_with_no_cycle(self):
fourth = Test.LinkedListNode(4)
third = Test.LinkedListNode(3, fourth)
second = Test.LinkedListNode(2, third)
first = Test.LinkedListNode(1, second)
result = contains_cycle(first)
self.assertFalse(result)
def test_cycle_loops_to_beginning(self):
fourth = Test.LinkedListNode(4)
third = Test.LinkedListNode(3, fourth)
second = Test.LinkedListNode(2, third)
first = Test.LinkedListNode(1, second)
fourth.next = first
result = contains_cycle(first)
self.assertTrue(result)
def test_cycle_loops_to_middle(self):
fifth = Test.LinkedListNode(5)
fourth = Test.LinkedListNode(4, fifth)
third = Test.LinkedListNode(3, fourth)
second = Test.LinkedListNode(2, third)
first = Test.LinkedListNode(1, second)
fifth.next = third
result = contains_cycle(first)
self.assertTrue(result)
def test_two_node_cycle_at_end(self):
fifth = Test.LinkedListNode(5)
fourth = Test.LinkedListNode(4, fifth)
third = Test.LinkedListNode(3, fourth)
second = Test.LinkedListNode(2, third)
first = Test.LinkedListNode(1, second)
fifth.next = fourth
result = contains_cycle(first)
self.assertTrue(result)
def test_empty_list(self):
result = contains_cycle(None)
self.assertFalse(result)
def test_one_element_linked_list_no_cycle(self):
first = Test.LinkedListNode(1)
result = contains_cycle(first)
self.assertFalse(result)
def test_one_element_linked_list_cycle(self):
first = Test.LinkedListNode(1)
first.next = first
result = contains_cycle(first)
self.assertTrue(result)
unittest.main(verbosity=2)
|
