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.

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 `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
nodes.add(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):
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
```

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

**one** will point to the head of the Linked List, and

**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):
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
```

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