Find the Length of a Cycle in a Linked List

89k
0

Given head of a singly linked list, return length of loop present in linked list. Return 0 when no loop exists.

A loop exists when next pointer of some node points to an earlier node in same linked list. Loop length equals number of distinct nodes inside cycle.

Example 1

Input: head = [1, 2, 3, 4, 5], pos = 1

Output: 4

Explanation: Tail connects to node at index 1, value 2. Loop nodes are [2, 3, 4, 5], so loop length equals 4.

Example 2

Input: head = [1, 2, 3, 4], pos = -1

Output: 0

Explanation: No node points back to an earlier node, so no loop exists.

Brute Force Approach

Hash set tracking stores visited node addresses during linked list traversal. A repeated address marks first node encountered again during traversal, proving presence of a loop and giving one node inside cycle.

Concepts include linked list traversal and hashing by object reference. After repeated node appears, one full traversal around cycle counts distinct loop nodes. The method is easy to reason about, but extra memory grows with number of visited nodes.

Algorithm

  • Initialize an empty hash set to store visited node addresses, as the node reference helps identify when the traversal reaches the same node again.

  • Traverse the linked list from head using a current pointer, since every reachable node needs to be checked for repetition.

  • Return 0 when current becomes NULL, as reaching the end means the linked list contains no loop.

  • Check whether the current node already exists in the hash set, as finding a previously visited node confirms the presence of a loop.

  • Store the current node as loopStart and initialize length as 1, since this node represents the first node counted in the loop.

  • Move current to the next node and continue traversing while it has not reached loopStart, incrementing length for every distinct node encountered in the loop.

  • Return length when current reaches loopStart again, as the number of steps taken represents the total number of nodes in the loop.

Dry Run

loop length hash set

loop length hash set

Solution

#include <bits/stdc++.h>
using namespace std;
class ListNode {
public:
int data;
ListNode* next;
// Constructor to create a linked list node.
ListNode(int value) {
data = value;
next = nullptr;
}
};
class Solution {
public:
// Function to find the length of a loop using visited nodes.
int lengthOfLoop(ListNode* head) {
// Stores every node visited during traversal.
unordered_set<ListNode*> visited;
// Start traversal from the head node.
ListNode* current = head;
// Continue until the end of the list or a repeated node is found.
while (current != nullptr) {
// A repeated node marks the beginning of the loop.
if (visited.find(current) != visited.end()) {
// Store the loop's starting node.
ListNode* start = current;
// The starting node is already counted.
int length = 1;
// Move to the next node inside the loop.
current = current->next;
// Count every remaining node until reaching the start.
while (current != start) {
length++;
current = current->next;
}
// Return the total number of nodes in the loop.
return length;
}
// Mark the current node as visited.
visited.insert(current);
// Move to the next node.
current = current->next;
}
// No repeated node means there is no loop.
return 0;
}
};
// Function to build a linked list from values and create a loop.
ListNode* buildList(vector<int>& values, int pos) {
// Return null when the input list is empty.
if (values.empty()) {
return nullptr;
}
// Create the first node as the head.
ListNode* head = new ListNode(values[0]);
ListNode* tail = head;
// Store the node where the loop should start.
ListNode* loopNode = (pos == 0) ? head : nullptr;
// Create the remaining nodes.
for (int index = 1; index < (int)values.size(); index++) {
// Create and attach the next node.
tail->next = new ListNode(values[index]);
tail = tail->next;
// Save the node at the given loop position.
if (index == pos) {
loopNode = tail;
}
}
// Connect the tail to the loop-start node when a loop is required.
if (pos != -1) {
tail->next = loopNode;
}
return head;
}
// Driver code.
int main() {
// Node values of the linked list.
vector<int> values = {1, 2, 3, 4, 5};
// Loop starts at index 1, so 5 points back to node 2.
int pos = 1;
// Build the linked list.
ListNode* head = buildList(values, pos);
// Create the solution object.
Solution sol;
// Find and print the length of the loop.

Complexity Analysis

Time Complexity: O(N), traversal visits each reachable node once before repetition or null, followed by one cycle traversal.

Space Complexity: O(N), hash set stores visited node addresses.

Optimal Approach

Floyd cycle detection uses two pointers moving at different speeds. Slow pointer moves one step, and fast pointer moves two steps. A loop forces both pointers to meet somewhere inside cycle because fast pointer gains one node of distance over slow pointer during each move inside cycle.

Concepts include slow-fast pointer traversal and cycle detection in linked lists. After meeting point appears, cycle length can be counted by keeping one pointer fixed at meeting point and moving another pointer around cycle until same node appears again. Extra storage remains constant.

Algorithm

  • Initialize slow and fast pointers at head, as they will move at different speeds to determine whether a cycle exists.

  • Move slow one node and fast two nodes while fast and fast->next exist, since this allows the traversal to continue safely while checking for a possible cycle.

  • Return 0 when fast or fast->next becomes NULL, as reaching the end confirms that no cycle exists.

  • Detect the loop when slow and fast meet, since two pointers moving at different speeds can meet again only when a cycle is present.

  • Initialize length as 1 and set a current pointer to the meeting node, as this node is the first node being counted in the cycle.

  • Move current to the next node and increment length while it has not returned to the meeting point, as each distinct node encountered represents one node in the cycle.

  • Return length when current reaches the meeting point again, since the number of steps taken gives the total length of the cycle.

Dry Run

loop-length-floyd-optimal1

loop-length-floyd-optimal1

Solution

#include <bits/stdc++.h>
using namespace std;
class ListNode {
public:
int data;
ListNode* next;
// Constructor to create a linked list node.
ListNode(int value) {
data = value;
next = nullptr;
}
};
class Solution {
public:
// Function to count the number of nodes in the loop.
int countLoopLength(ListNode* meetingPoint) {
// Start with the meeting node as the first loop node.
int length = 1;
// Move to the next node in the loop.
ListNode* current = meetingPoint->next;
// Continue until the meeting node is reached again.
while (current != meetingPoint) {
length++;
current = current->next;
}
// Return the total number of nodes in the loop.
return length;
}
// Function to find the loop length using slow and fast pointers.
int lengthOfLoop(ListNode* head) {
// Slow moves one node at a time.
ListNode* slow = head;
// Fast moves two nodes at a time.
ListNode* fast = head;
// Continue while fast can move two steps.
while (fast != nullptr && fast->next != nullptr) {
// Move slow by one node.
slow = slow->next;
// Move fast by two nodes.
fast = fast->next->next;
// A meeting point confirms the presence of a loop.
if (slow == fast) {
return countLoopLength(slow);
}
}
// Fast reached the end, so there is no loop.
return 0;
}
};
// Function to build a linked list from values and create a loop.
ListNode* buildList(vector<int>& values, int pos) {
// Return null when the input list is empty.
if (values.empty()) {
return nullptr;
}
// Create the first node as the head.
ListNode* head = new ListNode(values[0]);
ListNode* tail = head;
// Store the node where the loop should start.
ListNode* loopNode = (pos == 0) ? head : nullptr;
// Create the remaining nodes.
for (int index = 1; index < (int)values.size(); index++) {
// Create and attach the next node.
tail->next = new ListNode(values[index]);
tail = tail->next;
// Save the node at the given loop position.
if (index == pos) {
loopNode = tail;
}
}
// Connect the tail to the loop-start node when a loop is required.
if (pos != -1) {
tail->next = loopNode;
}
return head;
}
// Driver code.
int main() {
// Node values of the linked list.
vector<int> values = {1, 2, 3, 4, 5};
// Loop starts at index 1, so 5 points back to node 2.
int pos = 1;
// Build the linked list.
ListNode* head = buildList(values, pos);
// Create the solution object.

Complexity Analysis

Time Complexity: O(N), slow-fast traversal and cycle counting together remain linear in number of reachable nodes.

Space Complexity: O(1), only fixed pointer and counter variables are used.

Interview follow-up Questions

No. A singly linked list can contain at most one loop because each node has only one next pointer. Multiple independent loops cannot exist in the same linked list.

Linked List

Read Similar Blogs

Linked List

Swap Nodes in Pairs

Given the head of a singly linked list, swap every two adjacent nodes and return the modified head. Node values must stay inside the original nodes, so the task swaps node links instead of rewritin...

59.9k
Linked List

Merge Two Sorted Linked Lists

Given heads of two sorted linked lists, merge both lists into one sorted linked list and return the head of the merged list. Every node stores an integer value and a pointer to the next node. The f...

114.6k
Linked List

Find pairs with given sum in Doubly Linked List

Given a sorted doubly linked list containing positive distinct integers and an integer target, find every pair of node values whose sum equals target. Return pairs in increasing order based on the...

101.5k
Comments0