How would you find if there is a loop in a linked list from which node The loop starts?

Detect loop in a linked list

Given a linked list, check if the linked list has loop or not. Below diagram shows a linked list with a loop.

Table of Contents Show

• Detect loop in a linked list
• Explanation on finding the starting node of a loop in Linked List
• Detect loop in a Linked list
• Detecting a loop
• Detecting start of the loop

Recommended: Please solve it on “PRACTICE” first, before moving on to the solution.

The following are different ways of doing this.

Solution 1: HashingApproach:

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

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; }; void push(struct Node** head_ref, int new_data) { /* allocate node */ struct Node* new_node = new Node; /* put in the data */ new_node->data = new_data; /* link the old list off 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; } // This code is contributed by Geetanjali

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 d) { data = d; 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 their 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.

Python3

# Python3 program to detect loop # in the linked list # Node class class Node: # Constructor to initialize # the node object def __init__(self, data): self.data = data 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 have already has # this node in hashmap it # means their is a cycle # (Because you we 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.

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 d) { data = d; 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 their 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(val) { this.data = val; 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 their 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>

Output Loop found

Complexity Analysis:

• 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 hashmap.

Solution 2: This problem can be solved without hashmap by modifying the linked list data structure.
Approach: This solution requires modifications to the basic linked list data structure.

• 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. This solution works in O(n) but requires additional information with each node.
• A variation of this solution that doesn’t require modification to basic data structure can be implemented using a hash, just store the addresses of visited nodes in a hash and if you see an address that already exists in hash then there is a loop.

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; }; void push(struct Node** head_ref, int new_data) { /* allocate node */ struct Node* new_node = new Node; /* put in the data */ new_node->data = new_data; new_node->flag = 0; /* link the old list off 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

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; }; static Node push(Node head_ref, int new_data) { // Allocate node Node new_node = new Node(); // Put in the data new_node.data = new_data; new_node.flag = 0; // Link the old list off 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

Python3

# Python3 program to detect loop in a linked list ''' Link list node ''' class Node: def __init__(self): self.data = 0 self.next = None self.flag = 0 def push(head_ref, new_data): ''' allocate node ''' new_node = Node(); ''' put in the data ''' new_node.data = new_data; new_node.flag = 0; ''' link the old list off 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") # This code is contributed by rutvik_56

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; }; static Node push(Node head_ref, int new_data) { // Allocate node Node new_node = new Node(); // Put in the data new_node.data = new_data; new_node.flag = 0; // Link the old list off 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() { let data; let next; let flag; } } 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 off 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>

Output Loop found

Complexity Analysis:

• Time complexity:O(n).
  Only one traversal of the loop is needed.
• Auxiliary Space:O(1).
  No extra space is needed.

Solution 3: Floyd’s Cycle-Finding Algorithm
Approach: This is the fastest method and has been described below:

• 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 linked list doesn’t have a loop.

The below image shows how the detectloop 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; }; void push(Node** head_ref, int new_data) { /* allocate node */ Node* new_node = new Node(); /* put in the data */ new_node->data = new_data; /* link the old list off 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 rathbhupendra

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 off 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 class LinkedList { Node head; // head of list /* Linked list Node*/ class Node { int data; Node next; Node(int d) { data = d; 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("Loop not found"); } /* 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, data): self.data = data 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 # 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 "Found Loop" 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 d) { data = d; 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(d) { this.data = d; 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("Loop not found<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

Complexity Analysis:

• Time complexity: O(n).
  Only one traversal of the loop is needed.
• Auxiliary Space:O(1).
  There is no space required.

How does above algorithm work?
Please See : How does Floyd’s slow and fast pointers approach work?
https://www.youtube.com/watch?v=Aup0kOWoMVg

Solution 4: Marking visited nodes without modifying the linked list data structure
In this method, 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 key; struct Node* next; }; Node* newNode(int key) { Node* temp = new Node; temp->key = key; temp->next = NULL; return temp; } // A utility function to print a linked list void printList(Node* head) { while (head != NULL) { cout << head->key << " "; 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; 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* nex = head->next; // Make next point to temp head->next = temp; // Get to the next node in the list head = nex; } 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) cout << "Loop Found"; else cout << "No Loop"; return 0; }

Java

// Java program to return first node of loop class GFG { static class Node { int key; Node next; }; static Node newNode(int key) { Node temp = new Node(); temp.key = key; temp.next = null; return temp; } // A utility function to print a linked list static void printList(Node head) { while (head != null) { System.out.print(head.key + " "); 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(); 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 nex = head.next; // Make next point to temp head.next = temp; // Get to the next node in the list head = nex; } return false; } // Driver code public static void main(String args[]) { 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; boolean found = detectLoop(head); if (found) System.out.println("Loop Found"); else System.out.println("No Loop"); } } // This code is contributed by Arnab Kundu

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, key): self.key = key self.left = None self.right = None # A utility function to print a linked list def printList(head): while (head != None): print(head.key, 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 nex = head.next # Make next point to temp head.next = temp # Get to the next node in the list head = nex 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

C#

// C# program to return first node of loop using System; public class GFG { public class Node { public int key; public Node next; }; static Node newNode(int key) { Node temp = new Node(); temp.key = key; temp.next = null; return temp; } // A utility function to print a linked list static void printList(Node head) { while (head != null) { Console.Write(head.key + " "); 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(); 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 nex = head.next; // Make next point to temp head.next = temp; // Get to the next node in the list head = nex; } return false; } // Driver code public static void Main(String[] args) { 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; Boolean found = detectLoop(head); if (found) { Console.WriteLine("Loop Found"); } else { Console.WriteLine("No Loop"); } } } // This code is contributed by Princi Singh

Javascript

<script> // Javascript program to return first node of loop class Node { constructor(key) { this.key = key; this.nexy = 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 nex = 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>

Output Loop Found

Complexity Analysis:

• Time complexity: O(n).
  Only one traversal of the loop is needed.
• Auxiliary Space: O(1).
  There is no space required.

Solution 5: Store length

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

C++

// C++ program to return first node of loop #include <bits/stdc++.h> using namespace std; struct Node { int key; struct Node* next; }; Node* newNode(int key) { Node* temp = new Node; temp->key = key; temp->next = NULL; return temp; } // A utility function to print a linked list void printList(Node* head) { while (head != NULL) { cout << head->key << " "; 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; 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) cout << "Loop Found"; else cout << "No Loop Found"; return 0; }

Java

// Java program to return first node of loop import java.util.*; class GFG { static class Node { int key; Node next; }; static Node newNode(int key) { Node temp = new Node(); temp.key = key; temp.next = null; return temp; } // A utility function to print a linked list static void printList(Node head) { while (head != null) { System.out.print(head.key + " "); 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(); 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 = 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; boolean found = detectLoop(head); if (found) System.out.print("Loop Found"); else System.out.print("No Loop Found"); } } // This code is contributed by gauravrajput1

Python3

# Python program to return first node of loop class newNode: def __init__(self, key): self.key = key self.left = None self.right = None # A utility function to print a linked list def printList(head): while (head != None) : print(head.key, 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

C#

// C# program to return first node of loop using System; public class GFG { public class Node { public int key; public Node next; }; static Node newNode(int key) { Node temp = new Node(); temp.key = key; temp.next = null; return temp; } // A utility function to print a linked list static void printList(Node head) { while (head != null) { Console.Write(head.key + " "); 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) { // Create a temporary node Node temp = new 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; /*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 = 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) Console.Write("Loop Found"); else Console.Write("No Loop Found"); } } // This code is contributed by gauravrajput1

Javascript

<script> // Javascript program to return first node of loop class Node { constructor(key) { this.key = key; this.next = null; } } function newNode(key) { let temp = new Node(key); return temp; } // A utility function to print a linked list function printList(head) { while (head != null) { document.write(head.key + " "); 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 = 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; let found = detectLoop(head); if (found) document.write("Loop Found"); else document.write("No Loop Found"); // This code is contributed by divyeshrabadiya07 </script>

Output Loop Found

Complexity Analysis:

• Time complexity: O(n2)
• Auxiliary Space: O(1)

Another Approach:

1. This is the simplest approach of the given problem, the only thing we have to do is to assign a new value to each data of node in the linked list which is not in the range given.
2. Example suppose (1 <= Data on Node <= 10^3) then after visiting node assign the data as -1 as it is out of the given range.

Follow the code given below for a better understanding:

C++

// C++ program to return first node of loop #include <bits/stdc++.h> using namespace std; struct Node { int key; struct Node* next; }; Node* newNode(int key) { Node* temp = new Node; temp->key = key; temp->next = NULL; return temp; } // Function to detect first node of loop // in a linked list that may contain loop bool detectLoop(Node* head) { // If the head is null we will return false if (!head) return 0; else { // Traversing the linked list // for detecting loop while (head) { // If loop found if (head->key == -1) { return true; } // Changing the data of visited node to any // value which is outside th given range here it // is supposed the given range is (1 <= Data on // Node <= 10^3) else { head->key = -1; head = head->next; } } // If loop not found return false return 0; } } /* 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); cout << found << endl; return 0; }

Java

// Java program to return first node of loop import java.util.*; class LinkedList{ // Head of list static Node head; // Linked list Node static class Node { int data; Node next; Node(int d) { data = d; 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; } // Function to detect first node of loop // in a linked list that may contain loop static boolean detectLoop(Node h) { // If the head is null we will return false if (head == null) return false; else { // Traversing the linked list // for detecting loop while (head != null) { // If loop found if (head.data == -1) { return true; } // Changing the data of visited node to any // value which is outside th given range // here it is supposed the given range is (1 // <= Data on Node <= 10^3) else { head.data = -1; head = head.next; } } // If loop not found return false return false; } } // Driver Code public static void main(String[] args) { LinkedList llist = new LinkedList(); llist.push(1); llist.push(2); llist.push(3); llist.push(4); llist.push(5); /* Create a loop for testing */ llist.head.next.next.next.next.next = llist.head.next.next; if (detectLoop(llist.head)) System.out.println("1"); else System.out.println("0"); } } // This code is contributed by RohitOberoi

Python3

# Python program to return first node of loop class Node: def __init__(self,d): self.data = d self.next = None head = None def push(new_data): global head new_node = Node(new_data) new_node.next = head head=new_node def detectLoop(h): global head if (head == None): return False else: while (head != None): if (head.data == -1): return True else: head.data = -1 head = head.next return False push(1); push(2); push(3); push(4); push(5); head.next.next.next.next.next = head.next.next if (detectLoop(head)): print("1") else: print("0") # This code is contributed by patel2127.

C#

// C# program to return first node of loop using System; public class Node { public int data; public Node next; public Node(int d) { data = d; next = null; } } public class GFG{ // Head of list static Node head; /* 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; } // Function to detect first node of loop // in a linked list that may contain loop static bool detectLoop(Node h) { // If the head is null we will return false if (head == null) return false; else { // Traversing the linked list // for detecting loop while (head != null) { // If loop found if (head.data == -1) { return true; } // Changing the data of visited node to any // value which is outside th given range // here it is supposed the given range is (1 // <= Data on Node <= 10^3) else { head.data = -1; head = head.next; } } // If loop not found return false return false; } } // Driver Code static public void Main (){ push(1); push(2); push(3); push(4); push(5); /* Create a loop for testing */ head.next.next.next.next.next = head.next.next; if (detectLoop(head)) Console.WriteLine("1"); else Console.WriteLine("0"); } }

Javascript

<script> // Javascript program to return first node of loop // Linked list Node class Node { constructor(d) { this.data = d; this.next = null; } } // Head of list let head; /* 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 to detect first node of loop // in a linked list that may contain loop function detectLoop(h) { // If the head is null we will return false if (head == null) return false; else { // Traversing the linked list // for detecting loop while (head != null) { // If loop found if (head.data == -1) { return true; } // Changing the data of visited node to any // value which is outside th given range // here it is supposed the given range is (1 // <= Data on Node <= 10^3) else { head.data = -1; head = head.next; } } // If loop not found return false return false; } } // Driver Code push(1); push(2); push(3); push(4); push(5); /* Create a loop for testing */ head.next.next.next.next.next = head.next.next; if (detectLoop(head)) document.write("1"); else document.write("0"); // This code is contributed by unknown2108 </script>

Output 1

Time Complexity: O(N)

Auxiliary Space: O(1)

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

Article Tags :

Linked List

Accolite

Amazon

Linked Lists

loop

MAQ Software

Samsung

Tortoise-Hare-Approach

Practice Tags :

Accolite

Amazon

Samsung

MAQ Software

Linked List

Explanation on finding the starting node of a loop in Linked List

Given a linked list with loop, consider 2 pointers — one pointer (Slow pointer) moving with speed sand other pointer (Fast pointer) moving with speed 2*s. Given a loop in linked list, these two pointers will definitely meet at a point within loop.

Distance traveled by Slow pointer to reach meeting point:

Both slow and fast pointer takes same amount of time to reach the meeting point.

Too many equations here, right?

Let’s consider an example:

Notations( D represents x, K represents y and M represents z)

Here, x=8, y=1 and z=2

fast pointer runs in loop for 3 times till it reaches meeting point,hence t2=3

slow pointer reaches the meeting point before completing the loop, hence t1=0

from equation (i)

we know, x=8

let’s find the RHS and verify if LHS=RHS?

calculating value on RHS:

So, distance from head of linked list = distance from meeting point till both the pointers meet. If we start a pointer from head of the linked list and another one from meeting point then where will they meet?

loop: z+y

RHS: (t2-t1)*z+(t2-t1–1)*y (considered we are at meeting point)

Let’s change the perspective and take y steps back and we’ll reach the starting point of the loop, right?

now RHS becomes: (t2-t1)*z+(t2-t1–1)*y+y (considered we are at starting point, and since y distance was already covered by the pointer hence it wasn’t included. But now that we are changing the perspective of the problem and considering it to start from start of the loop we need to add y to the RHS. Simple math)

=> (t2-t1)*z+(t2-t1)*y

=> (t2-t1)*(y+z)

=>(t2-t1)*(loop)

Now this will always end up in the starting position no matter what t2 and t1 is as loop will be completed as whole.

and since LHS=RHS (as proved already)

So, it can be easily observed that if we start a pointer from head of the linked list and another from meeting point of the linked list, the pointers will cover same distance and meet at starting node of the list.

Here’s the implementation of above explained approach in java:

Time complexity is O(n) and Space complexity is O(1)

Happy coding and enjoy debugging :)

Detect loop in a Linked list

A loop in a linked list is a condition that occurs when the linked list does not have any end. When the loop exists in the linked list, the last pointer does not point to the Null as observed in the singly linked list or doubly linked list and to the head of the linked list observed in the circular linked list. When the loop exists, it points to some other node, also known as the linked list cycle.

Let's understand the loop through an example.

In the above figure, we can observe that the loop exists in the linked list. Here, the problem statement is that we have to detect the node, which is the start of the loop. The solution to solve this problem is:

• First, we detect the loop in the linked list.
• Detect the start node of the loop.

Detecting a loop

First, we will detect a loop in the linked list. To understand this, we will look at the algorithm for detecting a loop.

Step 1: First, we will initialize two pointers, i.e., S as a slow pointer and F as a fast pointer. Initially, both the pointers point to the first node in the linked list.

Step 2: Move the 'S' pointer one node at a time while move the 'F' pointer two nodes at a time.

Step 3: If at some point that both the pointers, i.e., 'S' and 'F, point to the same node, then there is a loop in the linked list; otherwise, no loop exists.

Let's visualize the above algorithm for more clarity.

As we can observe in the above figure that both the pointers, i.e., S and F point to the first node. Now, we will move the 'S' pointer by one and the 'F' pointer by two until they meet. If the 'F' pointer reaches the end node means that there is no loop in the linked list.

The 'S' pointer moves by one whereas the 'F' pointer moves by two, so 'S' pointer points to node 1, and the 'F' pointer points to node 9 shown as below:

Since both the pointers do not point to the same node and 'F' pointer does not reach the end node so we will again move both the pointers. Now, pointer 'S' will move to the node 9, and pointer 'F' will move to node 2, shown as below:

Since both the pointers do not point to the same node, so again, we will increment the pointers. Now, 'S' will point to node 4, and 'F' will point to the node 7 shown as below:

Since both the pointers do not point to the same node, so again, we will increment the pointers. Now, 'S' will point to the node 2, and 'F' will point to node 9 shown as below:

Since both the pointers do not point to the same node, so again, we will increment the pointers. Now, 'S' will point to node 3, and 'F' will also point to node 3 shown as below:

As we can observe in the above figure, both pointers point to the same node, i.e., 3; therefore, the loop exists in the linked list.

Detecting start of the loop

Here, we need to detect the origination of the loop. We will consider the same example which we discussed in detecting the loop. To detect the start of the loop, consider the below algorithm.

Step 1: Move 'S' to the start of the list, but 'F' would remain point to node 3.

Step 2: Move 'S' and 'F' forward one node at a time until they meet.

Step 3: The node where they meet is the start of the loop.

Let's visualize the above algorithm for more clarity.

First, we increment the pointer 'S' and 'F' by one; 'S' and 'F' would point to node 1 and node 7, respectively, shown as below:

Since both the node are not met, so we again increment the pointers by one node shown as below:

As we can observe in the above figure that the 'S' pointer points to node 9 and 'F' pointer points to the node 2. So again, we increment both the pointers by one node. Now, 'S' would point to the node 4, and 'F' would point to the node 9, shown as below:

As we can observe in the above figure that both the pointers do not point to the same node, so again, we will increment both the pointers by one node. Now, pointer 'S' and 'F' point to node 2 shown as below:

Since both the pointers point to the same node, i.e., 2; therefore, we conclude that the starting node of the loop is node 2.

Why this algorithm works?

Consider 'l' that denotes the length of the loop, which will measure the number in the links.

L: length of the loop

As we can observe in the above figure that there are five links.

Consider 'm' as the distance of the start of the loop from the beginning of the list. In other words, 'm' can be defined as the distance from the starting node to the node from where the loop gets started. So, in the above figure, m is 4 because the starting node is 8 and the node from the loop gets started is 2.

Consider 'k' is the distance of the meeting point of 'S' and 'F' from the start of the loop when they meet for the first time while detecting the loop. In the above linked list, the value of 'k' would be 1 because the node where both fast and slow pointers meet the first time is 3, and the node from where the loop has been started is 2.

When 'S' and 'F' meet for the first time then,

Let's assume that the total distance covered by the slow pointer is distance_S, and the total distance covered by the fast pointer is distance_F.

distance_S = m + p*l + k

where the total distance covered by S is the sum of the distance from the beginning of the list to the start of the loop, the distance covered by the slow pointer in the loop, and the distance from the start of the loop to the node where both the pointers meet.

distance_F = m + q*l + k (q>p since the speed of 'S' is greater than the speed of 'F')

As we know that when 'S' and 'F' met the first time, then 'F' traverses twice as faster as the 'S' pointer; therefore, the distance covered by 'F' would be two times the distance covered by 'S'. Mathematically, it can be represented as:

distance_F = 2distance_S

The above equation can be written as:

m + q*l + k = 2(m + p*l + k)

Solving the above equation, we would get:

m+k = (q-2p)*l, which implies that m+k is an integer multiple of l (length of the loop).

Implementation of detecting loop in C.

In the above code, detectloop() is the name of the function which will detect the loop in the linked list. We have passed the list pointer of type struct node pointing to the head node in the linked list. Inside the detectloop() function, we have declared two pointers, i.e., 'S' and 'F' of type struct node and assign the reference of the head node to these pointers. We define the while loop in which we are checking whether the 'S', 'F' and F->next are NULL or not. If they are not Null, then the control will go inside the while loop. Within the while loop, 'S' pointer is incremented by one node and 'F' pointer is incremented by two. If both 'F' and 'S' gets equal; means that the loop exists in the linked list.