from linked_list_prototype import ListNode
# @include
def has_cycle(head):
def cycle_len(end):
start, step = end, 0
while True:
step += 1
start = start.next
if start is end:
return step
fast = slow = head
while fast and fast.next and fast.next.next:
slow, fast = slow.next, fast.next.next
if slow is fast:
# Finds the start of the cycle.
cycle_len_advanced_iter = head
for _ in range(cycle_len(slow)):
cycle_len_advanced_iter = cycle_len_advanced_iter.next
it = head
# Both iterators advance in tandem.
while it is not cycle_len_advanced_iter:
it = it.next
cycle_len_advanced_iter = cycle_len_advanced_iter.next
return it # iter is the start of cycle.
return None # No cycle.
# @exclude
def simple_test():
L0 = ListNode(42)
L0.next = L0
assert has_cycle(L0)
L1, L2 = ListNode(42), ListNode(42)
L1.next, L2.next = L2, L1
assert has_cycle(L1) is L1
assert has_cycle(L2) is L2
L2.next = None
assert has_cycle(L1) is None
assert has_cycle(L2) is None
def main():
simple_test()
L3 = ListNode(3, None)
L2 = ListNode(2, L3)
L1 = ListNode(1, L2)
# Should output 'L1 does not have cycle.'
assert has_cycle(L1) is None
print('L1', 'has' if has_cycle(L1) else 'does not have', 'cycle.')
# Make it a cycle
L3.next = L2
# Should output 'L1 has cycle, at node has value 2'
assert has_cycle(L1) is not None
assert has_cycle(L1).data == 2
temp = has_cycle(L1)
if temp:
print('L1 has cycle, at node has value', temp.data)
else:
print('L1 does not have cycle')
if __name__ == '__main__':
main()