Open In App

Detect loop or cycle in a linked list

Last Updated : 02 Apr, 2024
Improve
Improve
Like Article
Like
Save
Share
Report

Given a linked list, check if the linked list has a loop (cycle) or not. The below diagram shows a linked list with a loop. 

Linked List with Loop

Detect loop in a linked list using Hashing:

The idea is to insert the nodes in the hashmap and whenever a node is encountered that is already present in the hashmap then return true.

Follow the steps below to solve the problem:

  • Traverse the list individually and keep putting the node addresses in a Hash Table. 
  • At any point, if NULL is reached then return false 
  • If the next of the current nodes points to any of the previously stored nodes in  Hash then return true.

Below is the implementation of the above approach:

C++ 
// C++ program to detect loop in a linked list
#include <bits/stdc++.h>
using namespace std;

/* Link list node */
struct Node {
    int data;
    struct Node* next;
      
      Node(int x) {
        data = x;
          next = NULL;
    }
};

void push(struct Node** head_ref, int new_data)
{
    /* allocate node and put in the data*/
    struct Node* new_node = new Node(new_data);

    /* link the old list of the new node */
    new_node->next = (*head_ref);

    /* move the head to point to the new node */
    (*head_ref) = new_node;
}

// Returns true if there is a loop in linked list
// else returns false.
bool detectLoop(struct Node* h)
{
    unordered_set<Node*> s;
    while (h != NULL) {
        // If this node is already present
        // in hashmap it means there is a cycle
        // (Because you will be encountering the
        // node for the second time).
        if (s.find(h) != s.end())
            return true;

        // If we are seeing the node for
        // the first time, insert it in hash
        s.insert(h);

        h = h->next;
    }

    return false;
}

/* Driver program to test above function*/
int main()
{
    /* Start with the empty list */
    struct Node* head = NULL;

    push(&head, 20);
    push(&head, 4);
    push(&head, 15);
    push(&head, 10);

    /* Create a loop for testing */
    head->next->next->next->next = head;

    if (detectLoop(head))
        cout << "Loop Found";
    else
        cout << "No Loop";

    return 0;
}
Java 
// Java program to detect loop in a linked list
import java.util.*;

public class LinkedList {

    static Node head; // head of list

    /* Linked list Node*/
    static class Node {
        int data;
        Node next;
        Node(int x)
        {
            data = x;
            next = null;
        }
    }

    /* Inserts a new Node at front of the list. */
    static public void push(int new_data)
    {
        /* 1 & 2: Allocate the Node &
                  Put in the data*/
        Node new_node = new Node(new_data);

        /* 3. Make next of new Node as head */
        new_node.next = head;

        /* 4. Move the head to point to new Node */
        head = new_node;
    }

    // Returns true if there is a loop in linked
    // list else returns false.
    static boolean detectLoop(Node h)
    {
        HashSet<Node> s = new HashSet<Node>();
        while (h != null) {
            // If we have already has this node
            // in hashmap it means there is a cycle
            // (Because you we encountering the
            // node second time).
            if (s.contains(h))
                return true;

            // If we are seeing the node for
            // the first time, insert it in hash
            s.add(h);

            h = h.next;
        }

        return false;
    }

    /* Driver program to test above function */
    public static void main(String[] args)
    {
        LinkedList llist = new LinkedList();

        llist.push(20);
        llist.push(4);
        llist.push(15);
        llist.push(10);

        /*Create loop for testing */
        llist.head.next.next.next.next = llist.head;

        if (detectLoop(head))
            System.out.println("Loop Found");
        else
            System.out.println("No Loop");
    }
}

// This code is contributed by Arnav Kr. Mandal.
C# 
// C# program to detect loop in a linked list
using System;
using System.Collections.Generic;

class LinkedList {

    // head of list
    public Node head;

    /* Linked list Node*/
    public class Node {
        public int data;
        public Node next;
        public Node(int x)
        {
            data = x;
            next = null;
        }
    }

    /* Inserts a new Node at front of the list. */
    public void push(int new_data)
    {
        /* 1 & 2: Allocate the Node &
                Put in the data*/
        Node new_node = new Node(new_data);

        /* 3. Make next of new Node as head */
        new_node.next = head;

        /* 4. Move the head to point to new Node */
        head = new_node;
    }

    // Returns true if there is a loop in linked
    // list else returns false.
    public static bool detectLoop(Node h)
    {
        HashSet<Node> s = new HashSet<Node>();
        while (h != null) {
            // If we have already has this node
            // in hashmap it means there is a cycle
            // (Because you we encountering the
            // node second time).
            if (s.Contains(h))
                return true;

            // If we are seeing the node for
            // the first time, insert it in hash
            s.Add(h);

            h = h.next;
        }

        return false;
    }

    /* Driver code*/
    public static void Main(String[] args)
    {
        LinkedList llist = new LinkedList();

        llist.push(20);
        llist.push(4);
        llist.push(15);
        llist.push(10);

        /*Create loop for testing */
        llist.head.next.next.next.next = llist.head;

        if (detectLoop(llist.head))
            Console.WriteLine("Loop Found");
        else
            Console.WriteLine("No Loop");
    }
}

// This code has been contributed by 29AjayKumar
Javascript 
<script>

// JavaScript program to detect loop in a linked list 
    var head; // head of list

    /* Linked list Node */
    class Node {
        constructor(x) {
            this.data = x;
            this.next = null;
        }
    }
    /* Inserts a new Node at front of the list. */
      function push(new_data) {
        /*
         * 1 & 2: Allocate the Node & Put in the data
         */
var new_node = new Node(new_data);

        /* 3. Make next of new Node as head */
        new_node.next = head;

        /* 4. Move the head to point to new Node */
        head = new_node;
    }

    // Returns true if there is a loop in linked
    // list else returns false.
    function detectLoop(h) {
        var s = new Set();
        while (h != null) {
            // If we have already has this node
            // in hashmap it means there is a cycle
            // (Because you we encountering the
            // node second time).
            if (s.has(h))
                return true;

            // If we are seeing the node for
            // the first time, insert it in hash
            s.add(h);

            h = h.next;
        }

        return false;
    }

    /* Driver program to test above function */
    

        push(20);
        push(4);
        push(15);
        push(10);

        /* Create loop for testing */
        head.next.next.next.next = head;

        if (detectLoop(head))
            document.write("Loop Found");
        else
            document.write("No Loop");

// This code is contributed by todaysgaurav

</script>
Python3 
# Python3 program to detect loop
# in the linked list

# Node class
class Node:

    # Constructor to initialize
    # the node object
    def __init__(self, x):
        self.data = x
        self.next = None


class LinkedList:

    # Function to initialize head
    def __init__(self):
        self.head = None

    # Function to insert a new
    # node at the beginning
    def push(self, new_data):
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node

    # Utility function to print it
    # the linked LinkedList
    def printList(self):
        temp = self.head
        while(temp):
            print(temp.data, end=" ")
            temp = temp.next

    def detectLoop(self):
        s = set()
        temp = self.head
        while (temp):

            # If we already have
            # this node in hashmap it
            # means there is a cycle
            # (Because we are encountering
            # the node second time).
            if (temp in s):
                return True

            # If we are seeing the node for
            # the first time, insert it in hash
            s.add(temp)

            temp = temp.next

        return False


# Driver program for testing
llist = LinkedList()
llist.push(20)
llist.push(4)
llist.push(15)
llist.push(10)

# Create a loop for testing
llist.head.next.next.next.next = llist.head

if(llist.detectLoop()):
    print("Loop Found")
else:
    print("No Loop ")

# This code is contributed by Gitanjali.

Output
Loop Found

Time complexity: O(N), Only one traversal of the loop is needed.
Auxiliary Space: O(N), N is the space required to store the value in the hashmap.

Detect loop in a linked list by Modification In Node Structure:

The idea is to modify the node structure by adding flag in it and mark the flag whenever visit the node.

Follow the steps below to solve the problem:

  • Have a visited flag with each node.
  • Traverse the linked list and keep marking visited nodes.
  • If you see a visited node again then there is a loop.

Below is the implementation of the above approach.

C++ 
// C++ program to detect loop in a linked list
#include <bits/stdc++.h>
using namespace std;

/* Link list node */
struct Node {
    int data;
    struct Node* next;
    int flag;
  
      Node(int x) {
        data = x;
          next = NULL;
          flag = 0;
    }
};

void push(struct Node** head_ref, int new_data)
{
    /* allocate node */
    struct Node* new_node = new Node(new_data);
 
    /* link the old list of the new node */
    new_node->next = (*head_ref);

    /* move the head to point to the new node */
    (*head_ref) = new_node;
}

// Returns true if there is a loop in linked list
// else returns false.
bool detectLoop(struct Node* h)
{
    while (h != NULL) {
        // If this node is already traverse
        // it means there is a cycle
        // (Because you we encountering the
        // node for the second time).
        if (h->flag == 1)
            return true;

        // If we are seeing the node for
        // the first time, mark its flag as 1
        h->flag = 1;

        h = h->next;
    }

    return false;
}

/* Driver program to test above function*/
int main()
{
    /* Start with the empty list */
    struct Node* head = NULL;

    push(&head, 20);
    push(&head, 4);
    push(&head, 15);
    push(&head, 10);

    /* Create a loop for testing */
    head->next->next->next->next = head;

    if (detectLoop(head))
        cout << "Loop Found";
    else
        cout << "No Loop";

    return 0;
}
// This code is contributed by Geetanjali
C 
// C program to detect loop in a linked list
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

/* Link list node */
typedef struct Node {
    int data;
    struct Node* next;
    int flag;
} Node;

void push(struct Node** head_ref, int new_data)
{
    /* allocate node */
    struct Node* new_node = (Node*)malloc(sizeof(Node));

    /* put in the data */
    new_node->data = new_data;

    new_node->flag = 0;

    /* link the old list of the new node */
    new_node->next = (*head_ref);

    /* move the head to point to the new node */
    (*head_ref) = new_node;
}

// Returns true if there is a loop in linked list
// else returns false.
bool detectLoop(struct Node* h)
{
    while (h != NULL) {
        // If this node is already traverse
        // it means there is a cycle
        // (Because you we encountering the
        // node for the second time).
        if (h->flag == 1)
            return true;

        // If we are seeing the node for
        // the first time, mark its flag as 1
        h->flag = 1;

        h = h->next;
    }

    return false;
}

/* Driver program to test above function*/
int main()
{
    /* Start with the empty list */
    struct Node* head = NULL;

    push(&head, 20);
    push(&head, 4);
    push(&head, 15);
    push(&head, 10);

    /* Create a loop for testing */
    head->next->next->next->next = head;

    if (detectLoop(head))
        printf("Loop Found");
    else
        printf("No Loop");

    return 0;
}

// This code is contributed by Aditya Kumar (adityakumar129)
Java 
// Java program to detect loop in a linked list
import java.util.*;

class GFG {

    // Link list node
    static class Node {
        int data;
        Node next;
        int flag;
        Node(int x)
        {
            data = x;
            next = null;
              flag = 0;
        }
    };

    static Node push(Node head_ref, int new_data)
    {

        // Allocate node
        Node new_node = new Node(new_data);

        // Link the old list of the new node
        new_node.next = head_ref;

        // Move the head to point to the new node
        head_ref = new_node;
        return head_ref;
    }

    // Returns true if there is a loop in linked
    // list else returns false.
    static boolean detectLoop(Node h)
    {
        while (h != null) {

            // If this node is already traverse
            // it means there is a cycle
            // (Because you we encountering the
            // node for the second time).
            if (h.flag == 1)
                return true;

            // If we are seeing the node for
            // the first time, mark its flag as 1
            h.flag = 1;

            h = h.next;
        }
        return false;
    }

    // Driver code
    public static void main(String[] args)
    {

        // Start with the empty list
        Node head = null;

        head = push(head, 20);
        head = push(head, 4);
        head = push(head, 15);
        head = push(head, 10);

        // Create a loop for testing
        head.next.next.next.next = head;

        if (detectLoop(head))
            System.out.print("Loop Found");
        else
            System.out.print("No Loop");
    }
}

// This code is contributed by Rajput-Ji
C# 
// C# program to detect loop in a linked list
using System;

class GFG {

    // Link list node
    class Node {
        public int data;
        public Node next;
        public int flag;
          public Node(int x)
        {
            data = x;
            next = null;
              flag = 0;
        }
    };

    static Node push(Node head_ref, int new_data)
    {

        // Allocate node
        Node new_node = new Node(new_data);

        // Link the old list of the new node
        new_node.next = head_ref;

        // Move the head to point to the new node
        head_ref = new_node;
        return head_ref;
    }

    // Returns true if there is a loop in linked
    // list else returns false.
    static bool detectLoop(Node h)
    {
        while (h != null) {

            // If this node is already traverse
            // it means there is a cycle
            // (Because you we encountering the
            // node for the second time).
            if (h.flag == 1)
                return true;

            // If we are seeing the node for
            // the first time, mark its flag as 1
            h.flag = 1;

            h = h.next;
        }
        return false;
    }

    // Driver code
    public static void Main(string[] args)
    {

        // Start with the empty list
        Node head = null;

        head = push(head, 20);
        head = push(head, 4);
        head = push(head, 15);
        head = push(head, 10);

        // Create a loop for testing
        head.next.next.next.next = head;

        if (detectLoop(head))
            Console.Write("Loop Found");
        else
            Console.Write("No Loop");
    }
}

// This code is contributed by pratham76
Javascript 
<script>

// JavaScript program to detect loop in a linked list

// Link list node
class Node
{
    constructor(x)
    {
        this.data = x;
        this.next = null;
        this.flag = 0;
        
    }
}

function push( head_ref, new_data)
{
    // Allocate node
    let new_node = new Node();
 
    // Put in the data
    new_node.data = new_data;
 
    new_node.flag = 0;
 
    // Link the old list of the new node
    new_node.next = head_ref;
 
    // Move the head to point to the new node
    head_ref = new_node;
    return head_ref;
}

// Returns true if there is a loop in linked
// list else returns false.    
function detectLoop(h)
{
    while (h != null)
    {
         
        // If this node is already traverse
        // it means there is a cycle
        // (Because you we encountering the
        // node for the second time).
        if (h.flag == 1)
            return true;
 
        // If we are seeing the node for
        // the first time, mark its flag as 1
        h.flag = 1;
 
        h = h.next;
    }
    return false;
}

// Driver code

// Start with the empty list
    let head = null;
 
    head = push(head, 20);
    head = push(head, 4);
    head = push(head, 15);
    head = push(head, 10);
 
    // Create a loop for testing
    head.next.next.next.next = head;
 
    if (detectLoop(head))
        document.write("Loop Found");
    else
        document.write("No Loop");



// This code is contributed by rag2127

</script>
Python3 
# Python3 program to detect loop in a linked list

''' Link list node '''


class Node:

    def __init__(self, x):
        self.data = x
        self.next = None
        self.flag = 0


def push(head_ref, new_data):
    ''' allocate node and put in the data'''
    new_node = Node(new_data)

    new_node.flag = 0

    ''' link the old list of the new node '''
    new_node.next = (head_ref)

    ''' move the head to point to the new node '''
    (head_ref) = new_node
    return head_ref

# Returns true if there is a loop in linked list
# else returns false.


def detectLoop(h):

    while (h != None):
        # If this node is already traverse
        # it means there is a cycle
        # (Because you we encountering the
        # node for the second time).
        if (h.flag == 1):
            return True

        # If we are seeing the node for
        # the first time, mark its flag as 1
        h.flag = 1
        h = h.next
    return False


''' Driver program to test above function'''
if __name__ == '__main__':

    ''' Start with the empty list '''
    head = None

    head = push(head, 20)
    head = push(head, 4)
    head = push(head, 15)
    head = push(head, 10)

    ''' Create a loop for testing '''
    head.next.next.next.next = head

    if (detectLoop(head)):
        print("Loop Found")
    else:
        print("No Loop")

Output
Loop Found

Time complexity: O(N), Only one traversal of the loop is needed.
Auxiliary Space: O(1)

Detect loop in a linked list using Floyd’s Cycle-Finding Algorithm:

This algorithm is used to find a loop in a linked list. It uses two pointers one moving twice as fast as the other one. The faster one is called the faster pointer and the other one is called the slow pointer.

Follow the steps below to solve the problem:

  • Traverse linked list using two pointers.
  • Move one pointer(slow_p) by one and another pointer(fast_p) by two.
  • If these pointers meet at the same node then there is a loop. If pointers do not meet then the linked list doesn’t have a loop.

Illustration:

The below image shows how the detect loop function works in the code:

Implementation of Floyd’s Cycle-Finding Algorithm:  

C++ 
// C++ program to detect loop in a linked list
#include <bits/stdc++.h>
using namespace std;

/* Link list node */
class Node {
public:
    int data;
    Node* next;
      Node(int x) {
        data = x;
          next = NULL;
    }
};

void push(Node** head_ref, int new_data)
{
    /* allocate node and put in the data*/
    Node* new_node = new Node(new_data);

    /* link the old list of the new node */
    new_node->next = (*head_ref);

    /* move the head to point to the new node */
    (*head_ref) = new_node;
}

int detectLoop(Node* list)
{
    Node *slow_p = list, *fast_p = list;

    while (slow_p && fast_p && fast_p->next) {
        slow_p = slow_p->next;
        fast_p = fast_p->next->next;
        if (slow_p == fast_p) {
            return 1;
        }
    }
    return 0;
}

/* Driver code*/
int main()
{
    /* Start with the empty list */
    Node* head = NULL;

    push(&head, 20);
    push(&head, 4);
    push(&head, 15);
    push(&head, 10);

    /* Create a loop for testing */
    head->next->next->next->next = head;
    if (detectLoop(head))
        cout << "Loop Found";
    else
        cout << "No Loop";
    return 0;
}

// This is code is contributed by Nidhi goel.
C 
// C program to detect loop in a linked list
#include <stdio.h>
#include <stdlib.h>

/* Link list node */
struct Node {
    int data;
    struct Node* next;
};

void push(struct Node** head_ref, int new_data)
{
    /* allocate node */
    struct Node* new_node
        = (struct Node*)malloc(sizeof(struct Node));

    /* put in the data  */
    new_node->data = new_data;

    /* link the old list of the new node */
    new_node->next = (*head_ref);

    /* move the head to point to the new node */
    (*head_ref) = new_node;
}

int detectLoop(struct Node* list)
{
    struct Node *slow_p = list, *fast_p = list;

    while (slow_p && fast_p && fast_p->next) {
        slow_p = slow_p->next;
        fast_p = fast_p->next->next;
        if (slow_p == fast_p) {
            return 1;
        }
    }
    return 0;
}

/* Driver program to test above function*/
int main()
{
    /* Start with the empty list */
    struct Node* head = NULL;

    push(&head, 20);
    push(&head, 4);
    push(&head, 15);
    push(&head, 10);

    /* Create a loop for testing */
    head->next->next->next->next = head;

    if (detectLoop(head))
        printf("Loop Found");
    else
        printf("No Loop");
    return 0;
}
Java 
// Java program to detect loop in a linked list

import java.io.*;

class LinkedList {
    Node head; // head of list

    /* Linked list Node*/
    class Node {
        int data;
        Node next;
        Node(int x)
        {
            data = x;
            next = null;
        }
    }

    /* Inserts a new Node at front of the list. */
    public void push(int new_data)
    {
        /* 1 & 2: Allocate the Node &
                Put in the data*/
        Node new_node = new Node(new_data);

        /* 3. Make next of new Node as head */
        new_node.next = head;

        /* 4. Move the head to point to new Node */
        head = new_node;
    }

    void detectLoop()
    {
        Node slow_p = head, fast_p = head;
        int flag = 0;
        while (slow_p != null && fast_p != null
               && fast_p.next != null) {
            slow_p = slow_p.next;
            fast_p = fast_p.next.next;
            if (slow_p == fast_p) {
                flag = 1;
                break;
            }
        }
        if (flag == 1)
            System.out.println("Loop Found");
        else
            System.out.println("No Loop");
    }

    /* Driver program to test above functions */
    public static void main(String args[])
    {
        LinkedList llist = new LinkedList();

        llist.push(20);
        llist.push(4);
        llist.push(15);
        llist.push(10);

        /*Create loop for testing */
        llist.head.next.next.next.next = llist.head;

        llist.detectLoop();
    }
}
/* This code is contributed by Rajat Mishra. */
Python 
# Python program to detect loop in the linked list

# Node class


class Node:

    # Constructor to initialize the node object
    def __init__(self, x):
        self.data = x
        self.next = None


class LinkedList:

    # Function to initialize head
    def __init__(self):
        self.head = None

    # Function to insert a new node at the beginning
    def push(self, new_data):
        new_node = Node(new_data)
        new_node.next = self.head
        self.head = new_node

    # Utility function to print it the linked LinkedList
    def printList(self):
        temp = self.head
        while(temp):
            print(temp.data)
            temp = temp.next

    def detectLoop(self):
        slow_p = self.head
        fast_p = self.head
        while(slow_p and fast_p and fast_p.next):
            slow_p = slow_p.next
            fast_p = fast_p.next.next
            if slow_p == fast_p:
                return 1
        return 0


# Driver program for testing
llist = LinkedList()
llist.push(20)
llist.push(4)
llist.push(15)
llist.push(10)

# Create a loop for testing
llist.head.next.next.next.next = llist.head
if(llist.detectLoop()):
    print("Loop Found")
else:
    print("No Loop")

# This code is contributed by Nikhil Kumar Singh(nickzuck_007)
C# 
// C# program to detect loop in a linked list
using System;

public class LinkedList {
    Node head; // head of list

    /* Linked list Node*/
    public class Node {
        public int data;
        public Node next;
        public Node(int x)
        {
            data = x;
            next = null;
        }
    }

    /* Inserts a new Node at front of the list. */
    public void push(int new_data)
    {
        /* 1 & 2: Allocate the Node &
                Put in the data*/
        Node new_node = new Node(new_data);

        /* 3. Make next of new Node as head */
        new_node.next = head;

        /* 4. Move the head to point to new Node */
        head = new_node;
    }

    Boolean detectLoop()
    {
        Node slow_p = head, fast_p = head;
        while (slow_p != null && fast_p != null
               && fast_p.next != null) {
            slow_p = slow_p.next;
            fast_p = fast_p.next.next;
            if (slow_p == fast_p) {
                return true;
            }
        }
        return false;
    }

    /* Driver code */
    public static void Main(String[] args)
    {
        LinkedList llist = new LinkedList();

        llist.push(20);
        llist.push(4);
        llist.push(15);
        llist.push(10);
        /*Create loop for testing */
        llist.head.next.next.next.next = llist.head;

        Boolean found = llist.detectLoop();
        if (found) {
            Console.WriteLine("Loop Found");
        }
        else {
            Console.WriteLine("No Loop");
        }
    }
}

// This code is contributed by Princi Singh
Javascript 
<script>

// Javascript program to detect loop in a linked list
let head; // head of list

/* Linked list Node*/
class Node 
{
    constructor(x)
    {
        this.data = x;
        this.next = null;
    }
}

/* Inserts a new Node at front of the list. */
function push(new_data)
{
    
    /* 1 & 2: Allocate the Node &
            Put in the data*/
    let new_node = new Node(new_data);

    /* 3. Make next of new Node as head */
    new_node.next = head;

    /* 4. Move the head to point to new Node */
    head = new_node;
}

function detectLoop()
{
    let slow_p = head, fast_p = head;
    let flag = 0;
    
    while (slow_p != null && fast_p != null && 
           fast_p.next != null)
    {
        slow_p = slow_p.next;
        fast_p = fast_p.next.next;
        if (slow_p == fast_p)
        {
            flag = 1;
            break;
        }
    }
    if (flag == 1)
        document.write("Loop Found<br>");
    else
        document.write("No Loop<br>");
}

// Driver code
push(20);
push(4);
push(15);
push(10);

// Create loop for testing 
head.next.next.next.next = head;

detectLoop();

// This code is contributed by avanitrachhadiya2155

</script>

Output
Loop Found

Time complexity: O(N), Only one traversal of the loop is needed.
Auxiliary Space: O(1). 

Detect loop in a linked list by Marking visited nodes without modifying Node structure:

The idea is to point the current node of the linked list to a node which is created. Whenever a node’s next is pointing to that node it means loop is there.

Follow the steps below to solve the problem:

  • A temporary node is created. 
  • The next pointer of each node that is traversed is made to point to this temporary node. 
  • This way we are using the next pointer of a node as a flag to indicate whether the node has been traversed or not. 
  • Every node is checked to see if the next is pointing to a temporary node or not.
  • In the case of the first node of the loop, the second time we traverse it this condition will be true, hence we find that loop exists. 
  • If we come across a node that points to null then the loop doesn’t exist.

Below is the implementation of the above approach:

C++ 
// C++ program to return first node of loop
#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    struct Node* next;
      Node(int x) {
        data = x;
          next = NULL;
    }
};

// A utility function to print a linked list
void printList(Node* head)
{
    while (head != NULL) {
        cout << head->data << " ";
        head = head->next;
    }
    cout << endl;
}

// Function to detect first node of loop
// in a linked list that may contain loop
bool detectLoop(Node* head)
{
    // Create a temporary node
    Node* temp = new Node(0);
    while (head != NULL) {
        // This condition is for the case when there is no
        // loop
        if (head->next == NULL)
            return false;
        // Check if next is already pointing to temp
        if (head->next == temp)
            return true;
        // Store the pointer to the next node
        // in order to get to it in the next step
        Node* next = head->next;
        // Make next point to temp
        head->next = temp;
        // Get to the next node in the list
        head = next;
    }
    return false;
}

/* Driver program to test above function*/
int main()
{
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);
    head->next->next->next = new Node(4);
    head->next->next->next->next = new Node(5);
    /* Create a loop for testing(5 is pointing to 3) */
    head->next->next->next->next->next = head->next->next;
    bool found = detectLoop(head);
    if (found)
        cout << "Loop Found";
    else
        cout << "No Loop";
    return 0;
}
C 
// C++ program to return first node of loop
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

Node* newNode(int x)
{
    Node* temp = (Node*)malloc(sizeof(Node));
    temp->data = x;
    temp->next = NULL;
    return temp;
}

// A utility function to print a linked list
void printList(Node* head)
{
    while (head != NULL) {
        printf("%d ", head->data);
        head = head->next;
    }
    printf("\n");
}

// Function to detect first node of loop
// in a linked list that may contain loop
bool detectLoop(Node* head)
{
    // Create a temporary node
    Node* temp = (Node*)malloc(sizeof(Node));
    while (head != NULL) {
        // This condition is for the case when there is no
        // loop
        if (head->next == NULL)
            return false;
        // Check if next is already pointing to temp
        if (head->next == temp)
            return true;
        // Store the pointer to the next node
        // in order to get to it in the next step
        Node* next = head->next;
        // Make next point to temp
        head->next = temp;
        // Get to the next node in the list
        head = next;
    }
    return false;
}

/* Driver program to test above function*/
int main()
{
    Node* head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(3);
    head->next->next->next = newNode(4);
    head->next->next->next->next = newNode(5);
    /* Create a loop for testing(5 is pointing to 3) */
    head->next->next->next->next->next = head->next->next;
    bool found = detectLoop(head);
    if (found)
        printf("Loop Found");
    else
        printf("No Loop");
    return 0;
}

// This code is contributed by Aditya Kumar (adityakumar129)
Java 
// Java program to return first node of loop
public class GFG {

    static class Node {
        int data;
        Node next;
          Node(int x) {
            data = x;
              next = null;
        }
    };
  
    // A utility function to print a linked list
    static void printList(Node head)
    {
        while (head != null) {
            System.out.print(head.data + " ");
            head = head.next;
        }
        System.out.println();
    }

    // Function to detect first node of loop
    // in a linked list that may contain loop
    static boolean detectLoop(Node head)
    {

        // Create a temporary node
        Node temp = new Node(0);
        while (head != null) {

            // This condition is for the case
            // when there is no loop
            if (head.next == null) {
                return false;
            }

            // Check if next is already
            // pointing to temp
            if (head.next == temp) {
                return true;
            }

            // Store the pointer to the next node
            // in order to get to it in the next step
            Node next = head.next;

            // Make next point to temp
            head.next = temp;

            // Get to the next node in the list
            head = next;
        }

        return false;
    }

    // Driver code
    public static void main(String args[])
    {
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);
        head.next.next.next.next = new Node(5);

        // Create a loop for testing(5 is pointing to 3) /
        head.next.next.next.next.next = head.next.next;

        boolean found = detectLoop(head);
        if (found)
            System.out.println("Loop Found");
        else
            System.out.println("No Loop");
    }
};

// This code is contributed by Arnab Kundu
C# 
// C# program to return first node of loop
using System;
public class GFG {

    public class Node {
        public int data;
        public Node next;
          public Node(int x) {
            data = x;
              next = null;
        }
    };

    // A utility function to print a linked list
    static void printList(Node head)
    {
        while (head != null) {
            Console.Write(head.data + " ");
            head = head.next;
        }
        Console.WriteLine();
    }

    // Function to detect first node of loop
    // in a linked list that may contain loop
    static Boolean detectLoop(Node head)
    {

        // Create a temporary node
        Node temp = new Node(0);
        while (head != null) {

            // This condition is for the case
            // when there is no loop
            if (head.next == null) {
                return false;
            }

            // Check if next is already
            // pointing to temp
            if (head.next == temp) {
                return true;
            }

            // Store the pointer to the next node
            // in order to get to it in the next step
            Node next = head.next;

            // Make next point to temp
            head.next = temp;

            // Get to the next node in the list
            head = next;
        }

        return false;
    }

    // Driver code
    public static void Main(String[] args)
    {
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);
        head.next.next.next.next = new Node(5);

        // Create a loop for testing(5 is pointing to 3)
        head.next.next.next.next.next = head.next.next;

        Boolean found = detectLoop(head);
        if (found) {
            Console.WriteLine("Loop Found");
        }
        else {
            Console.WriteLine("No Loop");
        }
    }
}
Javascript 
<script>

// Javascript program to return first node of loop
class Node
{
    constructor(x)
    {
        this.data = x;
        this.next = null;
    }
}

// A utility function to print a linked list
function printList(head)
{
     while (head != null)
    {
        document.write(head.key + " ");
        head = head.next;
    }
    document.write("<br>");
}

// Function to detect first node of loop
// in a linked list that may contain loop
function detectLoop(head)
{
    
    // Create a temporary node
    let temp = new Node();
    while (head != null) 
    {
        
        // This condition is for the case
        // when there is no loop
        if (head.next == null)
        {
            return false;
        }

        // Check if next is already
        // pointing to temp
        if (head.next == temp)
        {
            return true;
        }

        // Store the pointer to the next node
        // in order to get to it in the next step
        let next = head.next;

        // Make next point to temp
        head.next = temp;

        // Get to the next node in the list
        head = nex;
    }

    return false;
}

// Driver code
let head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(4);
head.next.next.next.next = new Node(5);

// Create a loop for testing(5 is pointing to 3) /
head.next.next.next.next.next = head.next.next;

let found = detectLoop(head);
if (found)
    document.write("Loop Found");
else
    document.write("No Loop");

// This code is contributed by ab2127

</script>
Python3 
# Python3 program to return first node of loop

# A binary tree node has data, pointer to
# left child and a pointer to right child
# Helper function that allocates a new node
# with the given data and None left and
# right pointers


class newNode:
    def __init__(self, x):
        self.data = x
        self.left = None

# A utility function to print a linked list


def printList(head):
    while (head != None):
        print(head.data, end=" ")
        head = head.next

    print()

# Function to detect first node of loop
# in a linked list that may contain loop


def detectLoop(head):

    # Create a temporary node
    temp = ""
    while (head != None):

        # This condition is for the case
        # when there is no loop
        if (head.next == None):
            return False

        # Check if next is already
        # pointing to temp
        if (head.next == temp):
            return True

        # Store the pointer to the next node
        # in order to get to it in the next step
        next = head.next

        # Make next point to temp
        head.next = temp

        # Get to the next node in the list
        head = next

    return False


# Driver Code
head = newNode(1)
head.next = newNode(2)
head.next.next = newNode(3)
head.next.next.next = newNode(4)
head.next.next.next.next = newNode(5)

# Create a loop for testing(5 is pointing to 3)
head.next.next.next.next.next = head.next.next

found = detectLoop(head)
if (found):
    print("Loop Found")
else:
    print("No Loop")

# This code is contributed by SHUBHAMSINGH10

Output
Loop Found

Time complexity: O(N). Only one traversal of the loop is needed.
Auxiliary Space: O(1) 

Detect loop in a linked list by Storing length:

The idea is to store the length of the list from first node and last node, increment last node till reaches NULL or number of nodes in last is greater the current between first and last nodes.

Follow the steps below to solve the problem:

  • In this method, two pointers are created, first (always points to head) and last. 
  • Each time the last pointer moves calculate no of nodes between the first and last. 
  • check whether the current no of nodes > previous no of nodes 
    • If yes we proceed by moving the last pointer 
    • Else it means we’ve reached the end of the loop, so return output accordingly.

Below is the implementation of the above approach:

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

struct Node {
    int data;
    struct Node* next;
      Node(int x) {
        data = x;
          next = NULL;
    }
};

// A utility function to print a linked list
void printList(Node* head)
{
    while (head != NULL) {
        cout << head->data << " ";
        head = head->next;
    }
    cout << endl;
}

/*returns distance between first and last node every time
 * last node moves forwards*/
int distance(Node* first, Node* last)
{
    /*counts no of nodes between first and last*/
    int counter = 0;

    Node* curr;
    curr = first;

    while (curr != last) {
        counter += 1;
        curr = curr->next;
    }

    return counter + 1;
}

// Function to detect first node of loop
// in a linked list that may contain loop
bool detectLoop(Node* head)
{

    // Create a temporary node
    Node* temp = new Node(0);

    Node *first, *last;

    /*first always points to head*/
    first = head;
    /*last pointer initially points to head*/
    last = head;

    /*current_length stores no of nodes between current
     * position of first and last*/
    int current_length = 0;

    /*prev_length stores no of nodes between previous
     * position of first and last*/
    int prev_length = -1;

    while (current_length > prev_length && last != NULL) {
        // set prev_length to current length then update the
        // current length
        prev_length = current_length;
        // distance is calculated
        current_length = distance(first, last);
        // last node points the next node
        last = last->next;
    }

    if (last == NULL) {
        return false;
    }
    else {
        return true;
    }
}

/* Driver program to test above function*/
int main()
{
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);
    head->next->next->next = new Node(4);
    head->next->next->next->next = new Node(5);

    /* Create a loop for testing(5 is pointing to 3) */
    head->next->next->next->next->next = head->next->next;

    bool found = detectLoop(head);
    if (found)
        cout << "Loop Found";
    else
        cout << "No Loop Found";

    return 0;
}
C 
// C program to return first node of loop
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

Node* newNode(int data)
{
    Node* temp = (Node*)malloc(sizeof(Node));
    temp->data = data;
    temp->next = NULL;
    return temp;
}

// A utility function to print a linked list
void printList(Node* head)
{
    while (head != NULL) {
        printf("%d ", head->data);
        head = head->next;
    }
    printf("\n");
}

/*returns distance between first and last node every time
 * last node moves forwards*/
int distance(Node* first, Node* last)
{
    /*counts no of nodes between first and last*/
    int counter = 0;

    Node* curr;
    curr = first;

    while (curr != last) {
        counter += 1;
        curr = curr->next;
    }

    return counter + 1;
}

// Function to detect first node of loop
// in a linked list that may contain loop
bool detectLoop(Node* head)
{
    // Create a temporary node
    Node* temp = (Node *)malloc(sizeof(Node));
    Node *first, *last;

    /*first always points to head*/
    first = head;
    /*last pointer initially points to head*/
    last = head;

    /*current_length stores no of nodes between current
     * position of first and last*/
    int current_length = 0;

    /*prev_length stores no of nodes between previous
     * position of first and last*/
    int prev_length = -1;

    while (current_length > prev_length && last != NULL) {
        // set prev_length to current length then update the
        // current length
        prev_length = current_length;
        // distance is calculated
        current_length = distance(first, last);
        // last node points the next node
        last = last->next;
    }

    if (last == NULL)
        return false;
    else
        return true;
}

/* Driver program to test above function*/
int main()
{
    Node* head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(3);
    head->next->next->next = newNode(4);
    head->next->next->next->next = newNode(5);

    /* Create a loop for testing(5 is pointing to 3) */
    head->next->next->next->next->next = head->next->next;

    bool found = detectLoop(head);
    if (found)
        printf("Loop Found");
    else
        printf("No Loop Found");

    return 0;
}

// This code is contributed by Aditya Kumar (adityakumar129)
Java 
// Java program to return first node of loop
import java.util.*;
class GFG
{
static class Node 
{
    int data;
    Node next;
      Node(int x) {
          data = x;
          next = null;
    }
};

// A utility function to print a linked list
static void printList(Node head)
{
    while (head != null)
    {
        System.out.print(head.data + " ");
        head = head.next;
    }
    System.out.println();
}

/*returns distance between first and last node every time
 * last node moves forwards*/
static int distance(Node first, Node last)
{
  
    /*counts no of nodes between first and last*/
    int counter = 0;
    Node curr;
    curr = first;
    while (curr != last) 
    {
        counter += 1;
        curr = curr.next;
    }
    return counter + 1;
}

// Function to detect first node of loop
// in a linked list that may contain loop
static boolean detectLoop(Node head)
{

    // Create a temporary node
    Node temp = new Node(0);
    Node first, last;

    /*first always points to head*/
    first = head;
  
    /*last pointer initially points to head*/
    last = head;

    /*current_length stores no of nodes between current
     * position of first and last*/
    int current_length = 0;

    /*current_length stores no of nodes between previous
     * position of first and last*/
    int prev_length = -1;
    while (current_length > prev_length && last != null)
    {
      
        // set prev_length to current length then update the
        // current length
          prev_length = current_length;
      
        // distance is calculated
        current_length = distance(first, last);
      
        // last node points the next node
        last = last.next;
    }
    
    if (last == null)
    {
        return false;
    }
    else
    { 
        return true;
    }
}

/* Driver program to test above function*/
public static void main(String[] args)
{
    Node head = new Node(1);
    head.next = new Node(2);
    head.next.next = new Node(3);
    head.next.next.next = new Node(4);
    head.next.next.next.next = new Node(5);

    /* Create a loop for testing(5 is pointing to 3) */
    head.next.next.next.next.next = head.next.next;
    boolean found = detectLoop(head);
    if (found)
        System.out.print("Loop Found");
    else
        System.out.print("No Loop Found");
}
}

// This code is contributed by gauravrajput1
C# 
// C# program to return first node of loop
using System;

public class GFG
{
  public
    class Node 
    {
      public int data;
      public Node next;
      public Node(int x) {
            data = x;
              next = null;
        }
    };

  // A utility function to print a linked list
  static void printList(Node head)
  {
    while (head != null)
    {
      Console.Write(head.data + " ");
      head = head.next;
    }
    Console.WriteLine();
  }

  /*returns distance between first and last node every time
 * last node moves forwards*/
  static int distance(Node first, Node last)
  {

    /*counts no of nodes between first and last*/
    int counter = 0;
    Node curr;
    curr = first;
    while (curr != last) 
    {
      counter += 1;
      curr = curr.next;
    }
    return counter + 1;
  }

  // Function to detect first node of loop
  // in a linked list that may contain loop
  static bool detectLoop(Node head)
  {
    Node first, last;

    /*first always points to head*/
    first = head;

    /*last pointer initially points to head*/
    last = head;

    /*current_length stores no of nodes between current
     * position of first and last*/
    int current_length = 0;

    /*current_length stores no of nodes between previous
     * position of first and last*/
    int prev_length = -1;
    while (current_length > prev_length && last != null)
    {

      // set prev_length to current length then update the
      // current length
      prev_length = current_length;

      // distance is calculated
      current_length = distance(first, last);

      // last node points the next node
      last = last.next;
    }

    if (last == null)
    {
      return false;
    }
    else
    { 
      return true;
    }
  }

  /* Driver program to test above function*/
  public static void Main(String[] args)
  {
    Node head = new Node(1);
    head.next = new Node(2);
    head.next.next = new Node(3);
    head.next.next.next = new Node(4);
    head.next.next.next.next = new Node(5);

    /* Create a loop for testing(5 is pointing to 3) */
    head.next.next.next.next.next = head.next.next;
    bool found = detectLoop(head);
    if (found)
      Console.Write("Loop Found");
    else
      Console.Write("No Loop Found");
  }
}
Javascript 
<script>

// Javascript program to return first node of loop
class Node 
{
    constructor(x) 
    {
        this.data = x;
        this.next = null;
    }
}


// A utility function to print a linked list
function printList(head)
{
    while (head != null)
    {
        document.write(head.data + " ");
        head = head.next;
    }
    document.write("</br>");
}

/*returns distance between first and last
node every time last node moves forwards*/
function distance(first, last)
{

    /*counts no of nodes between first and last*/
    let counter = 0;
    let curr;
    curr = first;
    
    while (curr != last)
    {
        counter += 1;
        curr = curr.next;
    }
    return counter + 1;
}

// Function to detect first node of loop
// in a linked list that may contain loop
function detectLoop(head)
{

    // Create a temporary node
    let temp = new Node();
    let first, last;
    
    /*first always points to head*/
    first = head;
    
    /*last pointer initially points to head*/
    last = head;
    
    /*current_length stores no of nodes
    between current position of first and last*/
    let current_length = 0;
    
    /*current_length stores no of nodes between
    previous position of first and last*/
    let prev_length = -1;
    
    while (current_length > prev_length &&
           last != null)
    {
    
        // Set prev_length to current length 
        // then update the current length
        prev_length = current_length;
        
        // Distance is calculated
        current_length = distance(first, last);
        
        // Last node points the next node
        last = last.next;
    }
    
    if (last == null)
    {
        return false;
    }
    else
    {
        return true;
    }
}

// Driver code
let head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.next.next.next = new Node(4);
head.next.next.next.next = new Node(5);

/* Create a loop for testing(5 is pointing to 3) */
head.next.next.next.next.next = head.next.next;
let found = detectLoop(head);
if (found)
    document.write("Loop Found");
else
    document.write("No Loop Found");
    
// This code is contributed by divyeshrabadiya07

</script>
Python3 
# Python program to return first node of loop
class newNode:
    def __init__(self, x):
        self.data = x
        self.left = None
        

# A utility function to print a linked list
def printList(head):

    while (head != None) :
        print(head.data, end=" ")
        head = head.next;
    
    print()


# returns distance between first and last node every time
# last node moves forwards
def distance(first, last):

    # counts no of nodes between first and last
    counter = 0

    curr = first

    while (curr != last):
        counter = counter + 1
        curr = curr.next
    

    return counter + 1

  
# Function to detect first node of loop
# in a linked list that may contain loop
def detectLoop(head):

    # Create a temporary node
    temp = ""

    # first always points to head
    first = head;
    # last pointer initially points to head
    last = head;

    # current_length stores no of nodes between current
    # position of first and last
    current_length = 0

    #current_length stores no of nodes between previous
    # position of first and last*/
    prev_length = -1

    while (current_length > prev_length and last != None) :
        # set prev_length to current length then update the
        # current length
        prev_length = current_length
        # distance is calculated
        current_length = distance(first, last)
        # last node points the next node
        last = last.next;
    
    
    if (last == None) :
        return False
    
    else : 
        return True
 

# Driver program to test above function

head = newNode(1);
head.next = newNode(2);
head.next.next = newNode(3);
head.next.next.next = newNode(4);
head.next.next.next.next = newNode(5);

# Create a loop for testing(5 is pointing to 3) 
head.next.next.next.next.next = head.next.next;

found = detectLoop(head)
if (found) :
    print("Loop Found")
else :
    print("No Loop Found")

# This code is contributed by ihritik

Output
Loop Found

Time complexity: O(N2), For every node calculate the length of that node from the head by traversing.
Auxiliary Space: O(1)




Like Article
Suggest improvement
Previous
Reverse a Doubly Linked List
Next
Find length of loop/cycle in given Linked List
Share your thoughts in the comments

Similar Reads

Detect Cycle in a Linked List using Map
Detect and Remove Loop in a Linked List
Find length of loop/cycle in given Linked List
Detect a negative cycle in a Graph | (Bellman Ford)
Detect cycle in the graph using degrees of nodes of graph
Detect cycle in Directed Graph using Topological Sort
Detect Cycle in a 2D grid
Detect a negative cycle in a Graph using Shortest Path Faster Algorithm
Detect Cycle in a Directed Graph
Detect cycle in an undirected graph
https://media.geeksforgeeks.org/auth/avatar.png
GeeksforGeeks
Article Tags :
Practice Tags :
We use cookies to ensure you have the best browsing experience on our website. By using our site, you acknowledge that you have read and understood our Cookie Policy & Privacy Policy
Lightbox