Find First Node of Loop in Linked List
Last Updated : 28 Aug, 2025
Given the head of a linked list, determine the starting node of the loop if a cycle exists. A loop occurs when the last node points back to an earlier node in the list. If no loop is present, return -1.
Example:
Input:
Output: 3
Explanation: The linked list contains a loop, and the first node of the loop is 3.
Input:
Output: -1
Explanation: No loop exists in the above linked list. So the output is -1.
[Naive approach] Using Hashing - O(n) Time and O(n) Space
The idea is to start traversing the Linked List from head node and while traversing insert each node into the HashSet. If there is a loop present in the Linked List, there will be a node which will be already present in the hash set.
- If there is a node which is already present in the HashSet, return the node value which represent the starting node of loop.
- else, if there is no node which is already present in the HashSet , then return -1.
C++ #include <iostream> #include <unordered_set> using namespace std; class Node { public: int data; Node* next; Node(int x) { data = x; next = nullptr; } }; int cycleStart(Node* head) { unordered_set<Node*> st; Node* currNode = head; // traverse the linked list while (currNode != nullptr) { // if the current node is already in the HashSet, // then this is the starting node of the loop if (st.find(currNode) != st.end()) { return currNode->data; } st.insert(currNode); currNode = currNode->next; } return -1; } 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); head->next->next->next->next->next = new Node(6); head->next->next->next->next->next = head->next->next; int loopNode = cycleStart(head); if (loopNode != -1) cout << loopNode; else cout << -1; return 0; } import java.util.HashSet; class Node { int data; Node next; Node(int x) { data = x; next = null; } } class GfG { static int cycleStart(Node head) { HashSet<Node> set = new HashSet<>(); Node currNode = head; // Traverse the linked list while (currNode != null) { // If current node already in set → loop start if (set.contains(currNode)) { return currNode.data; } set.add(currNode); currNode = currNode.next; } return -1; } 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); head.next.next.next.next.next = new Node(6); head.next.next.next.next.next = head.next.next; int loopNode = cycleStart(head); if (loopNode != -1) System.out.println(loopNode); else System.out.println(-1); } } class Node: def __init__(self, x): self.data = x self.next = None def cycleStart(head): visited = set() currNode = head # Traverse the linked list while currNode is not None: # If current node already in set → loop start if currNode in visited: return currNode.data visited.add(currNode) currNode = currNode.next return -1 if __name__ == "__main__": head = Node(1) head.next = Node(2) head.next.next = Node(3) head.next.next.next = Node(4) head.next.next.next.next = Node(5) head.next.next.next.next.next = Node(6) head.next.next.next.next.next = head.next.next loopNode = cycleStart(head) if loopNode != -1: print(loopNode) else: print(-1)
using System; using System.Collections.Generic; class Node { public int data; public Node next; public Node(int x) { data = x; next = null; } } class GfG { static int cycleStart(Node head) { HashSet<Node> visited = new HashSet<Node>(); Node currNode = head; // Traverse the linked list while (currNode != null) { // If current node already in set → loop start if (visited.Contains(currNode)) { return currNode.data; } visited.Add(currNode); currNode = currNode.next; } return -1; } 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); head.next.next.next.next.next = new Node(6); head.next.next.next.next.next = head.next.next; int loopNode = cycleStart(head); if (loopNode != -1) Console.WriteLine(loopNode); else Console.WriteLine(-1); } } class Node { constructor(x) { this.data = x; this.next = null; } } function cycleStart(head) { let visited = new Set(); let currNode = head; // Traverse the linked list while (currNode !== null) { // If current node already in set → loop start if (visited.has(currNode)) { return currNode.data; } visited.add(currNode); currNode = currNode.next; } return -1; } // 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); head.next.next.next.next.next = new Node(6); head.next.next.next.next.next = head.next.next; let loopNode = cycleStart(head); if (loopNode !== -1) console.log(loopNode); else console.log(-1); [Expected Approach] Using Floyd's loop detection algorithm - O(n) Time and O(1) Space
This approach can be divided into two parts:
1. Detect Loop in Linked List using Floyd’s Cycle Detection Algorithm:
This idea is to use Floyd’s Cycle-Finding Algorithm to find a loop in a linked list. It uses two pointers slow and fast, fast pointer move two steps ahead and slow will move one step ahead at a time.
Illustration:
2. Find Starting node of Loop:
After detecting that the loop is present using above algorithm, to find the starting node of loop in linked list, we will reset the slow pointer to head node and fast pointer will remain at its position. Both slow and fast pointers move one step ahead until fast not equals to slow. The meeting point will be the Starting node of loop.
Illustration:
For more details about the working & proof of this algorithm, Please refer to this article, How does Floyd’s Algorithm works.
C++ #include <iostream> using namespace std; class Node { public: int data; Node* next; Node(int x) { data = x; next = nullptr; } }; int cycleStart(Node* head) { // Initialize two pointers, slow and fast Node* slow = head; Node* fast = head; // Traverse the list while (fast != nullptr && fast->next != nullptr) { // Move slow pointer by one step slow = slow->next; // Move fast pointer by two steps fast = fast->next->next; // Detect loop if (slow == fast) { // Move slow to head, keep fast at meeting point slow = head; // Move both one step at a time until they meet while (slow != fast) { slow = slow->next; fast = fast->next; } // Return the meeting node, which // is the start of the loop return slow->data; } } // No loop found return -1; } 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); head->next->next->next->next->next = new Node(6); head->next->next->next->next->next = head->next->next; int loopNode = cycleStart(head); if (loopNode != -1) cout << loopNode; else cout << -1; return 0; } class Node { int data; Node next; Node(int x) { data = x; next = null; } } class GfG { static int cycleStart(Node head) { Node slow = head; Node fast = head; // Traverse the list while (fast != null && fast.next != null) { // Move slow pointer by one step slow = slow.next; // Move fast pointer by two steps fast = fast.next.next; if (slow == fast) { // Move slow to head // keep fast at meeting point slow = head; // Move both one step at a time until they meet while (slow != fast) { slow = slow.next; fast = fast.next; } // Return the meeting node's data, // which is the start of the loop return slow.data; } } return -1; } 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); head.next.next.next.next.next = new Node(6); head.next.next.next.next.next = head.next.next; int loopNode = cycleStart(head); if (loopNode != -1) System.out.println(loopNode); else System.out.println(-1); } } class Node: def __init__(self, x): self.data = x self.next = None def cycleStart(head): slow = head fast = head # Traverse the list while fast is not None and fast.next is not None: # Move slow by one step slow = slow.next # Move fast by two steps fast = fast.next.next # Detect loop if slow == fast: # Move slow to head # keep fast at meeting point slow = head # Move both one step at a time until they meet while slow != fast: slow = slow.next fast = fast.next # Return the meeting node's data return slow.data return -1 if __name__ == "__main__": head = Node(1) head.next = Node(2) head.next.next = Node(3) head.next.next.next = Node(4) head.next.next.next.next = Node(5) head.next.next.next.next.next = Node(6) head.next.next.next.next.next = head.next.next loopNode = cycleStart(head) if loopNode != -1: print(loopNode) else: print(-1)
using System; public class Node { public int data; public Node next; public Node(int x) { data = x; next = null; } } class GfG { static int cycleStart(Node head) { Node slow = head; Node fast = head; // Traverse the list while (fast != null && fast.next != null) { // Move slow pointer by one step slow = slow.next; // Move fast pointer by two steps fast = fast.next.next; // Detect loop if (slow == fast) { // Move slow to head // keep fast at meeting point slow = head; // Move both one step at a time until they meet while (slow != fast) { slow = slow.next; fast = fast.next; } // Return the meeting node's data return slow.data; } } return -1; } 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); head.next.next.next.next.next = new Node(6); head.next.next.next.next.next = head.next.next; int loopNode = cycleStart(head); if (loopNode != -1) Console.WriteLine(loopNode); else Console.WriteLine(-1); } } class Node { constructor(x) { this.data = x; this.next = null; } } function cycleStart(head) { let slow = head; let fast = head; // traverse the list while (fast !== null && fast.next !== null) { // move slow pointer by one step slow = slow.next; // move fast pointer by two steps fast = fast.next.next; // detect loop if (slow === fast) { // move slow to head, keep fast at meeting point slow = head; // move both one step at a time until they meet while (slow !== fast) { slow = slow.next; fast = fast.next; } // return the meeting node, which is // the start of the loop return slow; } } // no loop found return null; } // 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); head.next.next.next.next.next = new Node(6); head.next.next.next.next.next = head.next.next; const loopNode = cycleStart(head); if (loopNode) { console.log(loopNode.data); } else { console.log(-1); } Related articles:
Explore
DSA Fundamentals
Data Structures
Algorithms
Advanced
Interview Preparation
Practice Problem
My Profile