Linked List Cycle - JS Solution

Editorial

Editorial solutions and visualizations are prepared with care, but we do not guarantee 100% accuracy or completeness. Please use your own judgment to verify results. Visucodize is not responsible for decisions made based on this content.

const VISITED = 'visited', VISITED_COLOR = 'orange';
const CURR = 'curr', CURR_COLOR = 'blue';

function visMainFunction(inputArr, pos) {
    initClassProperties();
    importantWarningsNotification();
    explanationAndColorSchemaNotifications();
    
    startBatch();
    const head = convertInputToLinkedList(inputArr, pos);
    const list = new VisLinkedList(head, { dataPropName: 'val' });
    
    const visited = new VisSet().options({ labelExtractionPolicy: node => `Node(${node.val})` });
    visited.visManager.addClass(VISITED);
    endBatch();

    let current = head;

    while (current !== null) {
        startPartialBatch();

        const vm = list.makeVisManagerForNode(current);
        vm.addClass(CURR);
        notification(`Visiting the ${makeColoredSpan('current node', CURR_COLOR)}.`);

        if (visited.has(current)) {
            notification(`
                🚨 ${makeColoredSpan('Cycle detected!', 'red')}<br>
                The ${makeColoredSpan('current node', CURR_COLOR)} was already present in the 
                <code>visited</code> set — meaning we’ve encountered this exact node reference before.<br><br>
                This confirms the presence of a <b>cycle</b> in the linked list.
            `);
            endBatch();
            return true;
        }

        notification(`
            Marking the ${makeColoredSpan('current node', CURR_COLOR)} as <b>visited</b> 
            by adding it to the ${makeColoredSpan('<code>visited</code>', VISITED_COLOR)} set.<br><br>
            Proceeding to its <code>next</code> node.
        `);

        visited.add(current);
        vm.removeClass(CURR);
        vm.addClass(VISITED);

        current = current.next;
        endBatch();
    }

    notification(`✅ ${makeColoredSpan('No cycle found.', 'green')} Successfully reached the end of the linked list.`);
    return false;
}

function initClassProperties() {
    setClassProperties(VISITED, { backgroundColor: VISITED_COLOR });
    setClassProperties(CURR, { borderColor: CURR_COLOR, borderWidth: '2px' });
}

function explanationAndColorSchemaNotifications() {
  explanationNotification();
  notification(`
    🎨 <b>Color Schema</b><br><br>
    🔵 <b>${makeColoredSpan('Current node', CURR_COLOR)}</b> — the node currently being processed.<br>
    🟧 <b>${makeColoredSpan('Visited nodes', VISITED_COLOR)}</b> — nodes already encountered and stored in <code>visited</code>.
  `);
}

function convertInputToLinkedList(arr, pos) {
    if (arr.length === 0) return null;

    const nodes = arr.map(val => new ListNode(val));
    for (let i = 0; i < nodes.length - 1; i++) {
        nodes[i].next = nodes[i + 1];
    }
    if (pos >= 0) {
        nodes[nodes.length - 1].next = nodes[pos]; // create cycle
    }
    return nodes[0];
}

function ListNode(val, next = null) {
    this.val = val;
    this.next = next;
}

function importantWarningsNotification() {
  notification(`
    <h3>⚠️ Important Notes</h3>
    <ul>
      <li>
        💡 <b>Space-optimized alternative:</b><br>
        This approach uses extra memory for the <code>visited</code> set.  
        A memory-constant alternative is <b>Floyd’s Cycle Detection</b> (the
        <i>tortoise and hare</i> algorithm), which also detects cycles in <code>O(n)</code> time but with <code>O(1)</code> space.
      </li>
      <li>
        🧩 <b><code>pos</code> parameter clarification:</b><br>
        In LeetCode’s problem definition:<br>
        <i>
          “Internally, <code>pos</code> is used to denote the index of the node that tail’s
          <code>next</code> pointer is connected to. <b>Note that <code>pos</code> is not passed as a parameter.</b>”
        </i><br><br>
        In this visualization, however, <code>pos</code> <b>is passed</b> as an input argument — 
        but it serves <b>only</b> to help the input utility form the linked list by connecting the tail 
        to the specified node. It is <b>not</b> part of the actual cycle detection algorithm logic.
      </li>
    </ul>
  `);
}

Approach

⚠️ Important Notes

💡 Space-optimized alternative:
This approach uses extra memory for the visited set. A memory-constant alternative is Floyd’s Cycle Detection (the tortoise and hare algorithm), which also detects cycles in O(n) time but with O(1) space.
🧩 pos parameter clarification:
In LeetCode’s problem definition:
“Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.”

In this visualization, however, pos is passed as an input argument — but it serves only to help the input utility form the linked list by connecting the tail to the specified node. It is not part of the actual cycle detection algorithm logic.

Overview

We need to determine whether a singly linked list contains a cycle. A cycle exists if, while traversing via next pointers, we ever revisit the same node object again.

Traverse the list starting from head with a pointer current.
Maintain a Set named visited that stores node references we have already seen.
For each step:
- If current is already in visited, we have encountered the same node again → cycle detected (return true).
- Otherwise, add current to visited and move to current = current.next.
If we reach null, there is no cycle (return false).

Why This Works

In an acyclic list, each node is reached at most once, so we will eventually hit null. In a cyclic list, following next pointers should loop back to an already visited node. The check is done on the node objects themselves (references), not on their values.

Time Complexity

O(n) — where n is the number of nodes in the linked list. Each node (except the one where the cycle is detected, which will be encountered twice if a cycle exists) is visited at most once before we either detect a repeat or reach null.

Space Complexity

O(n) — where n is the number of nodes in the linked list. In the worst case (when there is no cycle), the visited set stores references to all n nodes.

Input-1

Linked List Cycle - JS Solution

Solution code

Solution explanation

Solution explanation

Approach

⚠️ Important Notes

Overview

Why This Works

Time Complexity

Space Complexity