×

Search anything:

# Find starting point of loop in linked list Get this book -> Problems on Array: For Interviews and Competitive Programming

In this article, we have explored three different algorithmic techniques to find starting point of loop in linked list.

Pre-requisites:

Contents

## Introduction

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. 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 `O(1)` time.

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.

### Code

Following is the implementation in Python:

``````def start_of_cycle1(node):
nodes = set()
while True:
if node in nodes:
return node
node = node.nex

print(start_of_cycle1(n1)) # will print 2
``````

### Complexity

The linked list has `N` number of nodes, and this algorithm looks at every node, therefore,

Time Complexity: `O(N)`

And since, while parsing through the linked list, this algorithm stores all those `N` nodes in a HashSet.
therefore,

Space Complexity: `O(N)`

## 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.

### Code

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 `visited` as `True` it will remain `True`, running the function again will return `n1` instead of `n2`.

We can fix this by reseting variable `visited` for every `Node`.

``````def start_of_cycle2(node):
while not node.visited:
node.visited = True
node = node.nex
result = node
# reseting values
return node
print(start_of_cycle2(n1)) # will print 2
print(start_of_cycle2(n1)) # will print 2
``````

### Complexity

Again now there are `N` number of Nodes and the Algorithm visits every node in the Linked List,
therefore,

Time Complexity: `O(N)`

And since, every needs an extra variable to be marked, so, we need `N` number of extra space,
therefore,

Space Complexity: `O(N)`

## 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 `1` and `2` steps.
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
``````

The Node `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,
another will point to the node, that was returned by the `tortoise_and_hare`.

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):
start = start.nex

common_point = tortoise_and_hare(n1)
print(start_of_cycle3(n1, common_point)) ## prints 2
``````

### Complexity

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 `O(N)`,
therefore,

Time Complexity: `O(N)`

And since, we're not creating any kind of extra memory,
therefore,

Space Complexity: `O(1)`

With this article at OpenGenus, you must have the complete idea of Finding starting point of loop in linked list. #### Shubhankar Maurya

Shubhankar Maurya is pursuing B.Sc in Computer Science from KD College, Mumbai University. He is an Intern at OpenGenus.

Find starting point of loop in linked list