Find starting point of loop in linked list

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

Pre-requisites:

• Hash Set
• Linked List

Contents

1. Introduction

• Methods
  1. Using HashSet
  2. Marking Node
  3. Floyd's (Tortoise and Hare) Algorithm

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.