Given a singly linked list, write a function that takes in the first node in a singly linked list and returns a boolean indicating if the linked list contains a “cycle”.
A cycle is when a node’s next point actually points back to a previous node in the list. This is also sometimes known as a circularly linked list.
The Linked List Node class code:
class Node(object): def __init__(self,value): self.value = value self.nextnode = None
To solve this problem we will have two markers traversing through the list. marker1 and marker2. We will have both makers begin at the first node of the list and traverse through the linked list. However, the second marker, marker2, will move two nodes ahead for every one node that marker1 moves.
By this logic, we can imagine that the markers are “racing” through the linked list, with marker2 moving faster. If the linked list has a cycle and is circularly connected we will have the analogy of a track, in this case, the marker2 will eventually be “lapping” the marker1 and they will equal each other.
If the linked list has no cycle, then marker2 should be able to continue on until the very end, never equaling the first marker.
Let’s see this logic coded out:
def cycle_check(node): # Begin both markers at the first node marker1 = node marker2 = node # Go until end of list while marker2 != None and marker2.nextnode != None: # Note marker1 = marker1.nextnode marker2 = marker2.nextnode.nextnode # Check if the markers have matched if marker2 == marker1: return True # Case where marker ahead reaches the end of the list return False
Test Your Solution
""" RUN THIS CELL TO TEST YOUR SOLUTION """ from nose.tools import assert_equal # CREATE CYCLE LIST a = Node(1) b = Node(2) c = Node(3) a.nextnode = b b.nextnode = c c.nextnode = a # Cycle Here! # CREATE NON CYCLE LIST x = Node(1) y = Node(2) z = Node(3) x.nextnode = y y.nextnode = z ############# class TestCycleCheck(object): def test(self,sol): assert_equal(sol(a),True) assert_equal(sol(x),False) print("ALL TEST CASES PASSED") # Run Tests t = TestCycleCheck() t.test(cycle_check)
ALL TEST CASES PASSED
Recommended: Understand The Singly Linked List and its Operation
Follow Me ❤😊
If you like my post please follow me to read my latest post on programming and technology.