In this article, we have explored three different algorithmic techniques to find starting point of loop in linked list.
You may know that every Node in a Linked List has two fields, one to store a value and one to point to another node, and this continues until a Node points to the Null Value.
Instead of pointing to the Null Value, the ending Node of the Linked List can point to the other ( one of the previous ) Node, and this may cause it to create a cycle in the Linked List.
Cycle in a Linked List could be considered as a problem ( Bug ) or a feature, as per your use case, and this article covers some algorithms that you can use to detect and find the Node where the cycle/loop occurs/starts in the Linked List.
A Linked List with a cycle may look like this, and we will be considering this linked-list through out this article.
First let's write a code for the above LinkedList with the cycle in it.
class Node: def __init__(self, val): self.val = val self.nex = None self.visited = False def __str__(self): return str(self.val) if __name__ == "__main__": (n1, n2, n3, n4, n5, n6) = (Node(1), Node(2), Node(3), Node(4), Node(5), Node(6)) n1.nex = n2 n2.nex = n3 n3.nex = n4 n4.nex = n5 n5.nex = n6 n6.nex = n2 # A cycle that goes to n2 # n1 -> n2 -> n3 -> n4 -> n5 -> n6 # ^ | # '-----------------------+ # # Testing should print 3 # print(n1.nex.nex) # works
Note: Consider this code to be common for all upcoming once.
We can use two kinds of methods,
- first in which we keep track of the Nodes that we have already visited once, and
- the second in which we do not keep track of the Nodes we visit and yet it tells you if linked list has cycle or not.
First two methods that we're going to look at are the ones that work on the basis of tracking their visits for each node. Hence, we're going to look at the ways to track nodes.
Storing in HashSet
One method for tracking is to store the Nodes that we have visited already in a HashSet So we can look up a node with
In this, first, we will define an empty
set() and then start a loop, which will run until we come to a Node which we have already added in the
set() while looping.
Following is the implementation in Python:
def start_of_cycle1(node): nodes = set() while True: if node in nodes: return node nodes.add(node) node = node.nex print(start_of_cycle1(n1)) # will print 2
The linked list has
N number of nodes, and this algorithm looks at every node, therefore,
And since, while parsing through the linked list, this algorithm stores all those
N nodes in a HashSet.
Marking the Nodes
Another way to keep track of the Nodes that we visited is to mark every Node, for this we're using a variable
visited in our code and every Node is a object with this variable.
Following is the implementation in Python:
def start_of_cycle2(node): while not node.visited: node.visited = True node = node.nex print(start_of_cycle2(n1)) # will print 2 print(start_of_cycle2(n1)) # will print 1
Now, you may notice that this method does have one issue, that is, that once we set
True it will remain
True, running the function again will return
n1 instead of
We can fix this by reseting variable
visited for every
def start_of_cycle2(node): head = node while not node.visited: node.visited = True node = node.nex result = node # reseting values while head.visited: head.visited = False head = head.nex return node print(start_of_cycle2(n1)) # will print 2 print(start_of_cycle2(n1)) # will print 2
Again now there are
N number of Nodes and the Algorithm visits every node in the Linked List,
And since, every needs an extra variable to be marked, so, we need
N number of extra space,
Tortoise and Hare Algorithm
This Algorithm was originally presented by Rober W. Floyd as to find the cycles in the directed graph, but we can use this Algorithm to find the cycles in linked list as well.
The first step in this algorithm is to check if there is a cycle or not.
For this, we consider two-pointer one which jumps with
1 steps in the list and the other pointer jumps with
2 steps in the list, and by theory, these two pointers should meet at one Node, if there is a Cycle available in the Linked-List.
Note: Jumps of these pointers don't need to be
It can be any number of steps, the only thing to consider here is that both pointers should take different number of steps.
def tortoise_and_hare(node): tortoise = node.nex hare = node.nex.nex while tortoise != hare: tortoise = tortoise.nex hare = hare.nex.nex return hare
tortoise_and_hare is returning, is the Node which will have the same distance from the starting point of the cycle, like the head of the Linked List.
Therefore, we can now consider two pointers,
one will point to the head of the Linked List, and
another will point to the node, that was returned by the
And now we can move both pointers by
1 step, until they point to the same Node, which is going to be the starting node of the cycle.
def start_of_cycle3(head, start): while start != head: head = head.nex start = start.nex return head common_point = tortoise_and_hare(n1) print(start_of_cycle3(n1, common_point)) ## prints 2
Now there are two pointers, one is moving forward by
1 step and another is moving forward by
2 steps and if this algorithm finds a cycle then they meet at a Node and this happens in
O(N) time and then
start_of_cycle3 iterates till the start of the cycle, which is about
And since, we're not creating any kind of extra memory,
With this article at OpenGenus, you must have the complete idea of Finding starting point of loop in linked list.