Minimal Node Identification within a Cyclic Linked List — Problem Statement & Solution Guide

Linked ListMediumFloyd's Cycle Detection

TimeO(n)

SpaceO(1)

Quick Answer & Algorithm Key Takeaway

Detect cycle using slow/fast pointers

TopicLinked List

PatternFloyd's Cycle Detection

TimeO(n)

SpaceO(1)

Problem Description

You are given the head of a singly linked list that may contain a cycle. Your task is to determine whether a cycle exists. If a cycle is present, identify the node within the cyclic portion that holds the smallest value and return that node. If the list has no cycle, return null. The list is defined by its nodes, each containing an integer value and a reference to the next node. A cycle occurs when a node’s next reference points to a previously visited node, creating a loop. The returned node must be one that lies on the loop; nodes outside the loop are irrelevant even if they hold smaller values. The function should operate in linear time and constant extra space.

Input: The linked list is described by an array of integers representing node values in order of appearance, and an integer pos indicating the zero‑based index of the node that the last node’s next pointer refers to. If pos is -1, the list has no cycle. Output: Return the integer value of the node with the minimum value among all nodes that belong to the cycle, or null if the list is acyclic.

DSA Pattern Breakdown

"Minimal Node Identification within a Cyclic Linked List"

medium

WHY DOES IT MATTER?

Cycle detection and in‑place analysis are fundamental for memory‑constrained environments, such as embedded systems or low‑latency services, where auxiliary data structures are costly or prohibited.

OPTIMIZATION CHALLENGE

The key insight is that once a cycle is confirmed, the loop length is bounded, allowing a single pass over the loop to compute any aggregate (here, the minimum) without revisiting nodes outside the cycle.

REAL-WORLD CONNECTION

In distributed systems, heartbeat messages form a logical linked list of node statuses; detecting a repeating pattern (a cycle) can indicate a routing loop, and identifying the minimal‑latency node within that loop helps break the loop efficiently.

During the interview, first implement the classic two‑pointer detection, then immediately reuse the meeting point to scan the loop; avoid extra containers and keep the code tight—this demonstrates mastery of constant‑space techniques.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

Detecting a cycle in a singly linked list is a classic problem solved optimally by Floyd's Tortoise and Hare algorithm, which uses two pointers moving at different speeds. The fast pointer advances two steps while the slow pointer advances one; if they ever meet, a cycle exists. Once a cycle is detected, the meeting point lies somewhere inside the loop, and we can traverse the entire loop starting from that point to locate the node with the minimum value. Naïve approaches, such as marking visited nodes with a hash set, require O(n) extra space and become prohibitive for massive lists, while repeatedly traversing the list to check for repeats leads to O(n^2) time. The optimal paradigm combines constant‑space cycle detection with a single linear scan of the loop, yielding O(n) time and O(1) auxiliary space.

Interview Questions on This Problem

Q1How does Floyd's Tortoise and Hare algorithm guarantee detection of a cycle without extra memory?

Because the fast pointer moves twice as quickly as the slow pointer, if a cycle exists the fast pointer will eventually lap the slow pointer within the loop, causing them to meet; if no cycle exists, the fast pointer reaches the list end (null) first.

Q2After detecting a cycle, how can you find the node with the smallest value in the cyclic portion in O(n) time and O(1) space?

Start from the meeting node, iterate through the cycle once (using a do‑while loop) while tracking the minimum value and its node; since the cycle length is at most n, this scan is linear and uses only a few scalar variables.

Q3Why is it unsafe to modify node pointers (e.g., setting next to null) during cycle detection in interview code?

Altering the original list can corrupt the data structure, violate problem constraints, and hide bugs; interviewers expect a solution that preserves the input, demonstrating respect for immutability and side‑effect‑free algorithms.

Examples

Example 1

Input

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

Output

Explanation: The list is 3→2→1→4→5. The tail (5) points to the node at index 2 (value 1), forming a cycle: 1→4→5→1. The nodes in the cycle have values {1,4,5}. The smallest value is 1, so the output is 1.

Example 2

Input

head=[10,20,30,40,50], pos=-1

Output

null

Explanation: The list has no cycle because pos is -1. Therefore, the function returns null.

Example 3

Input

head=[5,3,7,3,9], pos=1

Output

Explanation: The tail (9) points to the node at index 1 (value 3). The cycle is 3→7→3→9→3. The values in the cycle are {3,7,9}. The minimum is 3, so the output is 3.

Example 4

Input

head=[8,6,4,2], pos=0

Output

Explanation: The tail (2) points back to the head (index 0, value 8), creating a cycle that includes all nodes: 8→6→4→2→8. The values are {8,6,4,2}. The smallest value is 2, so the output is 2.

Constraints

1 <= n <= 10^5
-10^9 <= node.val <= 10^9
-1 <= pos < n
The list contains at most one cycle

Optimal Approach & Strategy

Use Floyd's Tortoise and Hare to detect a cycle in O(1) space; after detection, traverse the loop once from the meeting point to locate the minimum-valued node. The whole process stays linear in time.

Brute Force Approach

Store every visited node in a hash set while traversing; if you encounter a node already in the set, a cycle is found and you can then iterate from that node to find the minimum. This uses O(n) extra space and may require two passes over the list.

Code Solutions

Language:

JavaScript Solution

Time: O(n)

function minimalNodeIdentificationWithinACyclicLinkedList(head) {
  if (!head || !head.next) return null;
  let slow = head, fast = head;
  while (fast && fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      let minNode = slow;
      let curr = slow.next;
      while (curr !== slow) {
        if (curr.val < minNode.val) minNode = curr;
        curr = curr.next;
      }
      return minNode;
    }
  }
  // Check if a cycle exists but was not detected within the first three nodes
  if (fast && fast.next) {
    slow = head;
    while (slow !== fast) {
      slow = slow.next;
      fast = fast.next;
    }
    let minNode = slow;
    let curr = slow.next;
    while (curr !== slow) {
      if (curr.val < minNode.val) minNode = curr;
      curr = curr.next;
    }
    return minNode;
  }
  return null;
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* findMinInCycle(ListNode* head) {
        if (!head) return nullptr;
        ListNode *slow = head, *fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) {
                ListNode* minNode = slow;
                ListNode* curr = slow->next;
                while (curr != slow) {
                    if (curr->val < minNode->val) {
                        minNode = curr;
                    }
                    curr = curr->next;
                }
                return minNode;
            }
        }
        return nullptr;
    }
};

class Solution {
    public ListNode detectCycle(ListNode head) {
        if (!head || !head.next) {
            return null;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (slow != fast) {
            if (!fast || !fast.next) {
                return null;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        // Detect cycle and find start of cycle
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        // Find node with minimum value in cycle
        int min_val = Integer.MAX_VALUE;
        ListNode min_node = null;
        while (true) {
            if (slow.val < min_val) {
                min_val = slow.val;
                min_node = slow;
            }
            slow = slow.next;
            if (slow == fast) {
                break;
            }
        }
        return min_node;
    }
}

def detectCycle(head):
    if not head or not head.next:
        return None
    slow = head
    fast = head.next
    while slow != fast:
        if not fast or not fast.next:
            return None
        slow = slow.next
        fast = fast.next.next
    # Detect cycle and find start of cycle
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next
    # Find node with minimum value in cycle
    min_val = float('inf')
    min_node = None
    while True:
        if slow.val < min_val:
            min_val = slow.val
            min_node = slow
        slow = slow.next
        if slow == fast:
            break
    return min_node

function minimalNodeIdentificationWithinACyclicLinkedList(head) {
  if (!head || !head.next) return null;
  let slow = head, fast = head;
  while (fast && fast.next && fast.next.next) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow === fast) {
      let minNode = slow;
      let curr = slow.next;
      while (curr !== slow) {
        if (curr.val < minNode.val) minNode = curr;
        curr = curr.next;
      }
      return minNode;
    }
  }
  // Check if a cycle exists but was not detected within the first three nodes
  if (fast && fast.next) {
    slow = head;
    while (slow !== fast) {
      slow = slow.next;
      fast = fast.next;
    }
    let minNode = slow;
    let curr = slow.next;
    while (curr !== slow) {
      if (curr.val < minNode.val) minNode = curr;
      curr = curr.next;
    }
    return minNode;
  }
  return null;
}

Asked in Top Tech Interviews

Paytm

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.