Find the first node of the loop in a Linked List

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

Problem Statement

In this problem, we are given a linked list with a loop. We have to find the first node of the loop in the linked list.

Problem Statement Understanding

Let’s try to understand the problem statement with the help of examples.

Suppose the given list is:

  • According to the problem statement, we need to find the starting node of the loop.
  • From the linked list, we can see that there is a loop in the linked list starting at node with value 3 and containing 3 nodes 3, 5, and 7. The last node of the loop points back to the first node of the loop.
  • As node with value 3 is the first node of the loop, so we will return 3 as output.

If the given linked list is:

  • In this case, our loop comprises 6, 8, and 10 and the node with value 6 is the first node of the loop. So we will output 6.

Now, I think from the above examples, the problem statement is clear.

Before moving to the approach section, try to think about how you can approach this problem. What is the first thing that comes to your mind?

The very first thing that comes to mind is loop detection. Correct, but we can also use hashing to solve this problem.

  • The hashing solution will require O(n) space for the creation of the hash table, so we are first going to look at hashing approach, and then jump to the efficient loop detection approach.

Let us have a glance at the approach to get a clear look.

Approach and Algorithm (Hashing)

In this approach, we are going to use hashing to solve the problem. Well, how can hashing help us?

  • If we notice carefully, the first node of the loop is the first element that will appear twice while traversing the linked list with a loop.

1) We will first create a set, which will store the addresses of the nodes.
2) Now, we will traverse the given linked list. For every node, we will check if that node is present in the set or not.

  • If it is not present, then we will simply insert it into the set.
  • If the node is present in the set, it means that the current node is the first node of the loop. As the first node of the loop will be the first repeating node while traversing the list. So, if the node is present in the set, we will simply return that node.

This approach will work fine, but it requires extra O(n) space. So, now the main question is can we optimize this space?

  • The answer is yes, and we will see how we can optimize this space in the next approach.

Our next approach uses Floyd’s Cycle Detection algorithm.

Approach and Algorithm (Floyd’s Cycle Detection)

Our approach will be simple:
1) Firstly, we have to detect the loop in the given linked list.

  • For detecting a loop in any linked list, we know the most efficient algorithm is the Floyd Cycle detection Algorithm.

2) In Floyd's cycle detection algorithm, we initialize 2 pointers, slow and fast.

  • Both initially point to the head of the list.
  • The slow pointer jumps one place and the fast pointer jumps 2 places.
  • The node at which the slow and fast pointer meet is a loop node.

3) Now, after finding the loop node:

  • We will make 2 pointers ptr1 and ptr2, which will point to that loop node.
  • We will also initialize a variable to find the length of the loop. Now, how will we find the length of this loop?
    • ptr2 will be fixed, and we will increment ptr1 till it meets ptr2. As both are at the same position currently, when ptr1 will meet ptr2, the whole loop would've been traversed, and we will get the length k.

4) Now, as we have the length of the loop, we will make ptr1 and ptr2 point to the head again.

5) Now, we will shift ptr2 by k places.

6) After shifting, we will move both ptr1 and ptr2 simultaneously (taking 1 jump). The node at which ptr1 and ptr2 will meet will be the first node of the loop.

7) After finding the first node of the loop, we will return it.

Dry Run



Approach and Algorithm (More Optimized Approach)

In the previous method, after finding the loop node, we were also running a for loop to find the length of the loop in the linked list. Can we find the first node of loop without finding the length of loop?

  • The answer is Yes, and in this approach, we will see how we can do it.

This method will be very much similar to the previous one, but here we will try to avoid finding the length of loop.

1) Similar to the previous method, we will find the loop node using Floyd Cycle detection Algorithm.
2) After finding the loop node, we will initialize the slow pointer to the head of the linked list and the fast pointer will remain at its position.
3) Now we will start moving the fast and slow pointer one node at a time until they meet each other.
4) The node at which slow and fast meets will be the starting point or say the first node of the loop.

Now, let’s see the dry run for this approach.

Dry Run


Code Implementation

#include 
using namespace std;

/* Structure of a linked list node */
struct Node {
    int key;
    struct Node* next;
};

/* Using this we are creating a new list node */
Node* newNode(int key)
{
    Node* temp = new Node;
    temp->key = key;
    temp->next = NULL;
    return temp;
}

/* Using this function we will be printing the list */
void printList(Node* head)
{
    while (head != NULL) {
        cout << head->key << " ";
        head = head->next;
    }
    cout << endl;
}

/* Using this function we will find and return the first node of loop in the linked list */
Node* firstnode(Node* head)
{

    if (head == NULL || head->next == NULL)
        return NULL;

    Node *slow = head, *fast = head;

    slow = slow->next;
    fast = fast->next->next;

    while (fast && fast->next) {
        if (slow == fast)
            break;
        slow = slow->next;
        fast = fast->next->next;
    }

    if (slow != fast)
        return NULL;

    slow = head;
    while (slow != fast) {
        slow = slow->next;
        fast = fast->next;
    }

    return slow;
}

int main()
{
    Node* head = newNode(1);
    head->next = newNode(0);
    head->next->next = newNode(3);
    head->next->next->next = newNode(0);
    head->next->next->next->next = newNode(1);

    head->next->next->next->next->next = head->next;

    Node* res = firstnode(head);
    if (res == NULL)
        cout << "Loop does not exist";
    else
        cout << "Loop starting node is " << res->key;

    return 0;
}
import java.util.*;
public class PrepBytes{

/* Structure of a linked list node */
static class Node
{
    int key;
    Node next;
};

/* Using this we are creating a new list node */
static Node newNode(int key)
{
    Node temp = new Node();
    temp.key = key;
    temp.next = null;
    return temp;
}

/* Using this function we will be printing the list */
static void printList(Node head)
{
    while (head != null){
        System.out.print(head.key + " ");
        head = head.next;
    }
    System.out.println();
}

/* Using this function we will find and return the first node of loop in the linked list */
static Node firstnode(Node head)
{
    if (head == null || head.next == null)
    return null;
    
    Node slow = head, fast = head;
    
    slow = slow.next;
    fast = fast.next.next;
    
    while (fast != null && fast.next != null){
        if (slow == fast)
        break;
        
        slow = slow.next;
        fast = fast.next.next;
    }
    
    if (slow != fast)
    return null;

    slow = head;
    while (slow != fast){
        slow = slow.next;
        fast = fast.next;
    }
    
    return slow;
}

public static void main(String[] args)
{
    Node head = newNode(1);
    head.next = newNode(0);
    head.next.next = newNode(3);
    head.next.next.next = newNode(0);
    head.next.next.next.next = newNode(1);
    
    head.next.next.next.next.next = head.next;
    
    Node res = firstnode(head);
    if (res == null)
    System.out.print("Loop does not exist");
    else
    System.out.print("Loop starting node is " + res.key);
}
}

Output

Loop starting node is 0

Time Complexity: O(n), as no nested traversal is needed.

So, in this article, we have tried to explain the most efficient approach to find the first node of a loop in a linked list. Multiple concepts have been used here, so it makes this question an important one for coding interviews. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Previous post Deletion in Circular Linked List
Next post Delete a Doubly Linked List node at a given position

Leave a Reply

Your email address will not be published. Required fields are marked *