Starting point of loop in a Linked List

In this article, we will learn how to solve the most asked coding interview question: “Starting point of loop in a Linked List

Problem Statement: Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.

There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that the tail’s next pointer is connected to (0-indexed). It is -1 if there is no cycle. Note that pos is not passed as a parameter.

Do not modify the linked list.

Examples:

Example 1:
Input:
 head = [1,2,3,4,3,6,10]
Output:
 tail connects to node index 2
Explanation:
Example 2:
Input:
 head = [1,2]
Output:
 no cycle
Explanation:

Solution:

Solution 1: Brute Force

Approach:

We can store nodes in a hash table so that, if a loop exists, the head will encounter the same node again. This node will be present in the table and hence, we can detect the loop. Steps are:-

  • Iterate the given list.
  • For each node visited by head pointer, check if node is present in the hash table.
  • If yes, loop detected
  • If not, insert node in the hash table and move the head pointer ahead.
  • If head reaches null, then the given list does not have a cycle in it.

Dry Run:

We start iterating each node and storing nodes in the hash table if an element is not present.

Node(1) is not present in the hash table. So, we insert a node in it and move head ahead.

Node(2) is not present in the hash table. So, we insert a node in it and move head ahead.

Node(3) is not present in the hash table. So, we insert a node in it and move head ahead.

Node(4) is not present in the hash table. So, we insert a node in it and move head ahead.

Node(3) is not present in the hash table. So, we insert a node in it and move head ahead. Though this node contains 3 as a value, it is a different node than the node at position 3.

Node(6) is not present in the hash table. So, we insert a node in it and move head ahead.

Node(10) is not present in the hash table. So, we insert a node in it and move head ahead.

We reached the same node which was present in the hash table. Thus, the starting node of the cycle is node(3).

Code:

C++ Code

#include<bits/stdc++.h>
using namespace std;

class node {
    public:
        int num;
        node* next;
        node(int val) {
            num = val;
            next = NULL;
        }
};

void insertNode(node* &head,int val) {
    node* newNode = new node(val);
    if(head == NULL) {
        head = newNode;
        return;
    }
    node* temp = head;
    while(temp->next != NULL) temp = temp->next;
    
    temp->next = newNode;
    return;
}

void createCycle(node* &head,int pos) {
    node* ptr = head;
    node* temp = head;
    int cnt = 0;
    while(temp->next != NULL) {
        if(cnt != pos) {
            ++cnt;
            ptr = ptr->next;
        } 
        temp = temp->next;
    }
    temp->next = ptr;
}
//process as per mentioned in solution
node* detectCycle(node* head) {
    unordered_set<node*> st;
    while(head != NULL) {
        if(st.find(head) != st.end()) return head;
        st.insert(head);
        head = head->next;
    }
    return NULL;
}

int main() {
    node* head = NULL;
    
    insertNode(head,1);
    insertNode(head,2);
    insertNode(head,3);
    insertNode(head,4);
    insertNode(head,3);
    insertNode(head,6);
    insertNode(head,10);
    
    createCycle(head,2);
    
    node* nodeRecieve = detectCycle(head);
    if(nodeRecieve == NULL) cout<<"No cycle";
    else {
        node* temp = head;
        int pos = 0;
        while(temp!=nodeRecieve) {
            ++pos;
            temp = temp->next;
        }
        cout<<"Tail connects at pos "<<pos<<endl;
    }
    
    return 0;
}

Output: Tail connects at pos 2

Time Complexity: O(N)

Reason: Iterating the entire list once.

Space Complexity: O(N)

Reason: We store all nodes in a hash table.

Java Code

import java.util.*;
class Node {
        int num;
        Node next;
        Node(int val) {
            num = val;
            next = null;
        }
}
class TUF{
static Node insertNode(Node head,int val) {
    Node newNode = new Node(val);
    if(head == null) {
        head = newNode;
        return head;
    }
    Node temp = head;
    while(temp.next != null) temp = temp.next;
    
    temp.next = newNode;
    return head;
}

static void createCycle(Node head,int pos) {
    Node ptr = head;
    Node temp = head;
    int cnt = 0;
    while(temp.next != null) {
        if(cnt != pos) {
            ++cnt;
            ptr = ptr.next;
        } 
        temp = temp.next;
    }
    temp.next = ptr;
}
//process as per mentioned in solution
static Node detectCycle(Node head) {
    HashSet<Node> st=new HashSet<>();
    while(head != null) {
        if(st.contains(head)) return head;
        st.add(head);
        head = head.next;
    }
    return null;
}

public static void main(String args[]) {
    Node head = null;
    
    head=insertNode(head,1);
    head=insertNode(head,2);
    head=insertNode(head,3);
    head=insertNode(head,4);
    head=insertNode(head,3);
    head=insertNode(head,6);
    head=insertNode(head,10);
    
    createCycle(head,2);
    
    Node nodeRecieve = detectCycle(head);
    if(nodeRecieve == null) System.out.println("No cycle");
    else {
        Node temp = head;
        int pos = 0;
        while(temp!=nodeRecieve) {
            ++pos;
            temp = temp.next;
        }
        System.out.println("Tail connects at pos "+pos);
    }
    
}
}

Output: Tail connects at pos 2

Time Complexity: O(N)

Reason: Iterating the entire list once.

Space Complexity: O(N)

Reason: We store all nodes in a hash table.

Solution 2: Slow and Fast Pointer Method

Approach:

The following steps are required:

  • Initially take two pointers, fast and slow. Fast pointer takes two steps ahead while slow pointer will take single step ahead for each iteration.
  • We know that if a cycle exists, fast and slow pointers will collide.
  • If cycle does not exists, fast pointer will move to NULL
  • Else, when both slow and fast pointer collides, it detects a cycle exists.
  • Take another pointer, say entry. Point to the very first of the linked list.
  • Move the slow and the entry pointer ahead by single steps until they collide. 
  • Once they collide we get the starting node of the linked list.

But why use another pointer, entry?

Let’s say a slow pointer covers the L2 distance from the starting node of the cycle until it collides with a fast pointer. L1 be the distance traveled by the entry pointer to the starting node of the cycle. So, in total, the slow pointer covers the L1+L2 distance. We know that a fast pointer covers some steps more than a slow pointer. Therefore, we can say that a fast pointer will surely cover the L1+L2 distance. Plus, a fast pointer will cover more steps which will accumulate to nC length where cC is the length of the cycle and n is the number of turns. Thus, the fast pointer covers the total length of L1+L2+nC. 

We know that the slow pointer travels twice the fast pointer. So this makes equation to

2(L1+L2) = L1+L2+nC. This makes equation to

L1+L2 = nC. Moving L2 to the right side

L1 = nC-L2 and this shows why the entry pointer and the slow pointer would collide.

Dry Run:

We initialize fast and slow pointers to the head of the list. Fast moves two steps ahead and slowly takes a single step ahead.

We can see that the fast and slow pointer collides which shows the cycle exists. The entry pointer is pointed to the head of the list. And move them forward until it collides with the slow pointer.

We see that both collide and hence, we get the starting node of the list.

Code:

C++ Code

#include<bits/stdc++.h>
using namespace std;

class node {
    public:
        int num;
        node* next;
        node(int val) {
            num = val;
            next = NULL;
        }
};

void insertNode(node* &head,int val) {
    node* newNode = new node(val);
    if(head == NULL) {
        head = newNode;
        return;
    }
    node* temp = head;
    while(temp->next != NULL) temp = temp->next;
    
    temp->next = newNode;
    return;
}

void createCycle(node* &head,int pos) {
    node* ptr = head;
    node* temp = head;
    int cnt = 0;
    while(temp->next != NULL) {
        if(cnt != pos) {
            ++cnt;
            ptr = ptr->next;
        } 
        temp = temp->next;
    }
    temp->next = ptr;
}
//process as per mentioned in solution
node* detectCycle(node* head) {
    if(head == NULL||head->next == NULL) return NULL;
        
    node* fast = head;
    node* slow = head;
    node* entry = head;
        
    while(fast->next != NULL&&fast->next->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
            
        if(slow == fast) {
            while(slow != entry) {
                slow = slow->next;
                entry = entry->next;
            }
            return slow;
        }
    }
    return NULL;
}

int main() {
    node* head = NULL;
    
    insertNode(head,1);
    insertNode(head,2);
    insertNode(head,3);
    insertNode(head,4);
    insertNode(head,3);
    insertNode(head,6);
    insertNode(head,10);
    
    createCycle(head,2);
    
    node* nodeRecieve = detectCycle(head);
    if(nodeRecieve == NULL) cout<<"No cycle";
    else {
        node* temp = head;
        int pos = 0;
        while(temp!=nodeRecieve) {
            ++pos;
            temp = temp->next;
        }
        cout<<"Tail connects at pos "<<pos<<endl;
    }
    
    return 0;
}

Output: Tail connects at pos 2

Time Complexity: O(N)

Reason: We can take overall iterations club it to O(N)

Space Complexity: O(1)

Reason: No extra data structure is used.

Java Code

import java.util.*;
class Node {
        int num;
        Node next;
        Node(int val) {
            num = val;
            next = null;
        }
}
class TUF{
static Node insertNode(Node head,int val) {
    Node newNode = new Node(val);
    if(head == null) {
        head = newNode;
        return head;
    }
    Node temp = head;
    while(temp.next != null) temp = temp.next;
    
    temp.next = newNode;
    return head;
}

static void createCycle(Node head,int pos) {
    Node ptr = head;
    Node temp = head;
    int cnt = 0;
    while(temp.next != null) {
        if(cnt != pos) {
            ++cnt;
            ptr = ptr.next;
        } 
        temp = temp.next;
    }
    temp.next = ptr;
}
//process as per mentioned in solution
static Node detectCycle(Node head) {
    if(head == null||head.next == null) return null;
        
    Node fast = head;
    Node slow = head;
    Node entry = head;
        
    while(fast.next != null&&fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
            
        if(slow == fast) {
            while(slow != entry) {
                slow = slow.next;
                entry = entry.next;
            }
            return slow;
        }
    }
    return null;
}

public static void main(String args[]) {
    Node head = null;
    
    head=insertNode(head,1);
    head=insertNode(head,2);
    head=insertNode(head,3);
    head=insertNode(head,4);
    head=insertNode(head,3);
    head=insertNode(head,6);
    head=insertNode(head,10);
    
    createCycle(head,2);
    
    Node nodeRecieve = detectCycle(head);
    if(nodeRecieve == null) System.out.println("No cycle");
    else {
        Node temp = head;
        int pos = 0;
        while(temp!=nodeRecieve) {
            ++pos;
            temp = temp.next;
        }
        System.out.println("Tail connects at pos "+pos);
    }
    
}
}

Output: Tail connects at pos 2

Time Complexity: O(N)

Reason: We can take overall iterations club it to O(N)

Space Complexity: O(1)

Reason: No extra data structure is used.

Special thanks to Dewanshi Paul for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article