Senior 3 min · March 06, 2026

Floyd's Cycle Detection — Prevent Payment Gateway Outages

Q: When should I use a Dummy Node in a Linked List problem?

Use a dummy node whenever the 'head' of the linked list might be modified, deleted, or if you are building a new list from scratch (like in merging or partitioning). It simplifies code by ensuring the head is never a special case.

Q: What is the time complexity of finding the N-th node from the end?

Using the two-pointer offset pattern, the time complexity is $O(L)$ where $L$ is the length of the list, as you only need a single pass. The space complexity is $O(1)$ because you only store two pointers.

Q: Is it better to solve Linked List problems recursively or iteratively?

In an interview, the iterative approach is usually preferred because it uses $O(1)$ space. Recursion often uses $O(N)$ space due to the call stack, which can lead to a StackOverflowError on very large lists. However, recursion can produce cleaner code for problems like merging or reversing small lists.

Q: How can I detect if a linked list has a cycle and find its starting point?

Use Floyd's cycle detection: two pointers, slow and fast. If they meet, a cycle exists. To find the start, reset one pointer to head and advance both at the same speed; the node where they meet again is the start of the cycle.

Q: What is the trickiest linked list problem in interviews?

The 'clone a linked list with random pointers' is often considered tricky because it requires careful mapping of original nodes to cloned nodes without corrupting the random pointers. The interleaving approach (O(1) space) is a common advanced question.

A single cycle caused 100% CPU and repeated IDs in a payment gateway.

Naren · Founder

Plain-English first. Then code. Then the interview question.

About

● Production Incident 🔎 Debug Guide

⚡Quick Answer

Linked list problems test pointer manipulation and traversal logic — not algorithmic complexity.
Master 6 core patterns: Fast & Slow, Dummy Node, In-Place Reversal, Two Pointers (Offset), Recursion, and Merge logic.
Cycle detection with Floyd's algorithm runs in O(n) time and O(1) space.
Dummy nodes eliminate head-modification edge cases, reducing bugs by ~60%.
In production, a null-pointer bug in linked list traversal can silently corrupt data structures.
Biggest mistake: forgetting to update current pointer inside the loop — results in infinite loops.

Plain-English First

Imagine a treasure hunt where each clue tells you the location of the next clue — you can't jump to clue #5 without following the chain from clue #1. That's a linked list. Each item (node) holds some data AND a pointer to the next item. Unlike an array, you can't just say 'give me item 5' — you have to walk the chain. This makes some operations fast (inserting at the front) and others slow (finding the middle), which is exactly why interviewers love testing it.

Linked lists show up in almost every serious coding interview — not because companies build linked lists from scratch every day, but because they expose how clearly you think about pointers, edge cases, and traversal logic. Get one pointer wrong and your program crashes or loops forever. Get it right and you look like someone who actually understands memory. Linked list problems are the clearest signal interviewers have that you can reason about data structures, not just recite definitions.

The reason linked list problems trip people up isn't the data structure itself — it's the patterns. There are really only five or six fundamental techniques (two pointers, dummy nodes, reversal, recursion, merge logic) and once you recognize which pattern a problem is calling for, the solution practically writes itself. Without knowing the patterns, every new problem feels like starting from scratch.

By the end of this article you'll be able to: recognize which of the core linked list patterns applies to any problem you're given, implement all 10 classic problems cleanly in Java, avoid the null-pointer mistakes that trip up 80% of candidates, and explain your approach out loud — which is half of what interviewers are actually grading you on.

The Fast & Slow Pointer Pattern (Tortoise and Hare)

This is the most critical pattern for Linked List interviews. By moving two pointers at different speeds—one jumping one node at a time (slow) and another jumping two nodes (fast)—you can solve complex problems like cycle detection or finding the exact middle of a list in a single pass. This avoids the $O(N)$ space complexity of using a HashSet to track visited nodes.

io/thecodeforge/linkedlist/CycleDetector.javaJAVA

package io.thecodeforge.linkedlist;

/**
 * io.thecodeforge: Standard Floyd's Cycle-Finding Algorithm
 * Time Complexity: O(N), Space Complexity: O(1)
 */
public class CycleDetector {
    public boolean hasCycle(ListNode head) {
        if (head == null) return false;

        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {
                return true; // Cycle detected
            }
        }
        return false;
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

Output

// Returns true if the list contains a loop, false otherwise.

Forge Tip:

Type this code yourself rather than copy-pasting. The muscle memory of writing it will help it stick. Always handle the 'fast.next == null' check first to prevent the most common NullPointerException in this algorithm.

Production Insight

Cycle detection is often used for validation of linked lists in production systems. A cycle can cause an infinite loop that spikes CPU and blocks threads.

The fix: run Floyd's algorithm periodically on critical long-lived lists.

Rule: never trust a list that can be mutated — always validate with O(1) space.

Key Takeaway

The fast/slow pointer pattern solves cycle detection and middle-finding in one pass.

It's your go-to for O(1) space solutions.

If you can't use extra space, think fast/slow pointers first.

When to Use Fast & Slow Pointers

IfNeed to detect a cycle in a list

→

UseUse Floyd's algorithm — fast/slow pointers

IfNeed to find the middle node of a list

→

UseUse fast/slow pointers — when fast reaches end, slow is at middle

IfNeed to find the start of a cycle or calculate its length

→

UseExtend Floyd's: after collision, move one pointer to head and step both at same speed

The Dummy Node Pattern: Simplifying Edge Cases

When a problem requires you to delete nodes or merge two lists, the 'head' of your list might change. Instead of writing dozens of if (head == null) checks, we use a 'Dummy Node'. This serves as a permanent anchor point that sits just before the real head, making the logic for the first node identical to every other node in the list.

io/thecodeforge/linkedlist/MergeSortedLists.javaJAVA

package io.thecodeforge.linkedlist;

public class ListMerger {
    /**
     * io.thecodeforge: Merging two sorted linked lists using a Dummy Node
     */
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(-1);
        ListNode current = dummy;

        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                current.next = list1;
                list1 = list1.next;
            } else {
                current.next = list2;
                list2 = list2.next;
            }
            current = current.next;
        }

        current.next = (list1 != null) ? list1 : list2;
        return dummy.next;
    }
}

Output

// Input: 1->2->4, 1->3->4 | Output: 1->1->2->3->4->4

Pro Strategy:

Always remember to return 'dummy.next', not 'dummy'. The dummy is just a placeholder; its next pointer is where the real solution begins.

Production Insight

In production, using a dummy node eliminates the special case for the head. This reduces the chance of null pointer exceptions when deleting or inserting at the beginning.

Without a dummy node, you might accidentally lose the head reference after a deletion, causing a data leak.

Rule: use a dummy node whenever the head could be modified — it's the cheapest defensive programming.

Key Takeaway

Dummy node turns every node into a non-special case.

It eliminates the need for separate head handling.

Return dummy.next — never return dummy itself.

When to Use Dummy Node

IfMerging two sorted lists

→

UseUse dummy node to build the merged list from scratch

IfDeleting a node (especially the head) from a linked list

→

UseUse dummy node to make head deletion identical to any other node

IfPartitioning a list around a value

→

UseUse two dummy nodes (one for left, one for right) and merge at the end

In-Place Reversal Pattern

Reversing a linked list is a fundamental building block for many advanced problems (e.g., palindrome check, reverse in groups). The iterative approach uses three pointers: prev, current, and next. You iterate through the list, changing each node's next to point to the previous node. This reverses the list in-place with O(1) extra space.

io/thecodeforge/linkedlist/ReverseList.javaJAVA

package io.thecodeforge.linkedlist;

public class ReverseList {
    /**
     * io.thecodeforge: Iterative in-place reversal of a linked list.
     * Time: O(n), Space: O(1)
     */
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode current = head;
        
        while (current != null) {
            ListNode nextTemp = current.next; // store next
            current.next = prev;              // reverse pointer
            prev = current;                   // move prev forward
            current = nextTemp;               // move current forward
        }
        return prev; // prev becomes new head
    }
}

Output

// Input: 1->2->3->4->5 | Output: 5->4->3->2->1

Common Trap

Forgetting to store current.next before reassigning current.next = prev will lose the rest of the list. Always use a temporary variable.

Production Insight

Reversals are common in undo stacks or doubly linked list operations. In production, if you perform an in-place reversal and then cache the head, you'll have a reversed list cached — can cause unexpected behavior.

Always use a dummy or copy when you need to preserve the original list.

Rule: in-place reversal mutates the original — if you need it again, clone first.

Key Takeaway

Reversal is a three-pointer dance: prev, current, and nextTemp.

Never forget to save the next node before overwriting the pointer.

If you need to keep the original order, don't reverse in-place.

When to Reverse In-Place

IfNeed to check if a linked list is a palindrome

→

UseReverse the second half in-place (using middle-finding) and compare halves

IfReverse a linked list in groups of k

→

UseUse iterative reversal with a counter; after reversing a group, reconnect to previous group's tail

IfSimply reverse the entire list

→

UseUse three-pointer iteration (prev, current, nextTemp)

Two Pointers (Offset) Pattern — Finding the N-th Node from the End

When you need to find the N-th node from the end of a linked list, you can use a two-pointer technique with a fixed offset. Move one pointer N steps ahead, then move both pointers together until the leading pointer reaches the end. The trailing pointer will be at the N-th from the end. This solves the problem in one pass with O(1) space.

io/thecodeforge/linkedlist/NthFromEnd.javaJAVA

package io.thecodeforge.linkedlist;

public class NthFromEnd {
    /**
     * io.thecodeforge: Find the Nth node from the end of a linked list
     * Time: O(n), Space: O(1)
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode first = dummy;
        ListNode second = dummy;
        
        // Move first pointer n+1 steps ahead
        for (int i = 0; i <= n; i++) {
            if (first == null) return head; // n is larger than list length
            first = first.next;
        }
        
        // Move both pointers until first reaches end
        while (first != null) {
            first = first.next;
            second = second.next;
        }
        
        // second points to the (N-1)th node from end, remove its next
        second.next = second.next.next;
        return dummy.next;
    }
}

Output

// Input: 1->2->3->4->5, n=2 | Output: 1->2->3->5 (removes 4th node from end)

Edge Case Check

If n equals the length of the list, you'll remove the head. Using a dummy node ensures you handle this seamlessly.

Production Insight

This pattern is useful in stream processing when you need to look back N items from a forward-moving pointer. In production, be careful when n exceeds list length — return null or throw a meaningful error.

A common bug is off-by-one: move first pointer exactly n steps, not n+1 (if using dummy node).

Rule: when removing the N-th node from the end, use a dummy node and advance first pointer n+1 steps for zero-based indexing.

Key Takeaway

Two-pointer offset: move one pointer ahead by N steps, then walk both together.

The trailing pointer stops exactly N from the end.

Works for both finding and removing — perfect for single-pass problems.

When to Use Two Pointers (Offset)

IfFind the k-th node from the end

→

UseMove one pointer k steps ahead, then both at same speed

IfRemove the N-th node from the end (as in the code)

→

UseUse dummy node and move first pointer n+1 steps ahead

IfFind the middle of a list (without knowing length)

→

UseUse fast/slow pointers (different pattern)

Recursive Merge & Other Patterns

Recursion can elegantly solve linked list problems like merging two sorted lists or reversing the list. Although recursion uses O(N) stack space, it often leads to cleaner code. However, for large lists, prefer iterative to avoid stack overflow. The merge pattern combines two sorted list by recursing on the smaller head.

Other important patterns include: cloning a linked list with random pointers, and reversing in groups of k. These build on the core patterns above.

io/thecodeforge/linkedlist/RecursiveMerge.javaJAVA

package io.thecodeforge.linkedlist;

public class RecursiveMerge {
    /**
     * io.thecodeforge: Recursive merge of two sorted linked lists.
     * Time: O(n+m), Space: O(n+m) due to recursion stack.
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        
        if (l1.val <= l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

Output

// Input: 1->2->4, 1->3->4 | Output: 1->1->2->3->4->4

Think Like a LIFO Stack

Base case: one list is null -> return the other.
Recursive step: compare heads, attach smaller head to result of merging the rest.
Trust the recursion: it will correctly merge the tails.
Watch out for stack overflow on large lists (n > 1000).

Production Insight

In production, recursion depth is limited by the stack size. If you merge a list of 10,000 nodes recursively, you'll get a StackOverflowError.

Always prefer iterative over recursive for production code where list size is unbounded.

Rule: recursion for linked lists is elegant but dangerous at scale — use only when you control the input size.

Key Takeaway

Recursion reads clean but hides a stack memory cost.

Iterative merge with dummy node is production-safer.

Always state trade-offs in an interview: recursion = clarity, iteration = safety.

Recursion vs Iteration for Linked Lists

IfList size known and small (< 1000)

→

UseRecursion is fine, code is cleaner

IfList size unknown or large

→

UseUse iterative approach — avoid stack overflow

IfInterview setting where recursion simplifies explanation

→

UseStart with recursion, then mention iterative as optimization

● Production incidentPOST-MORTEMseverity: high

Cycle in a Linked List Brought Down a Payment Gateway

Symptom

Application became unresponsive. CPU pinned at 100% on a few nodes. Logs showed the same transaction IDs repeating in the history traversal.

Assumption

The linked list representing the transaction chain was acyclic — as it had always been during testing and QA.

Root cause

A bug in the code that appended new transactions to the list inadvertently created a cycle by pointing a new node's next back to an earlier node instead of null.

Fix

Implemented Floyd's cycle detection algorithm to validate the list integrity after each append operation. Added a periodic integrity check that warns if a cycle is detected.

Key lesson

Never assume a linked list is acyclic in production — validate with Floyd's algorithm after each mutation.
Add a cycle detection guard in any critical path that traverses a long-lived linked list.
Use health checks that verify list integrity to catch cycles before they cause outages.

Production debug guideQuick symptom-to-action guide for common linked list failures.3 entries

Symptom · 01

CPU spikes, application hangs, repeated log entries

→

Fix

Immediately suspect a cycle. Use Floyd's cycle detection algorithm on the list. If cycle found, isolate the node causing it and fix the mutation logic.

Symptom · 02

NullPointerException on node.next

→

Fix

Check if you are accessing node.next.next without verifying node.next != null. Add null checks before chaining. Validate the list length if possible.

Symptom · 03

Unexpected results from list traversal (missing nodes or wrong order)

→

Fix

Lost pointer reference during reversal or merge. Verify you are not overwriting a reference before using it. Use 'prev' and 'next' temporaries. Print the list after each operation to isolate the step.

★ Linked List Debug CommandsFor each symptom, run these commands to diagnose linked list issues in your running service.

Infinite loop or CPU at 100%−

Immediate action

Dump thread stacks to find hung thread.

Commands

kill -3 <java_pid>

grep -A20 'RUNNABLE' thread_dump.txt | head -40

Fix now

Add Floyd's cycle detection before the traversal loop and return false if cycle detected.

NullPointerException in linked list code+

List seems to have lost nodes or order is wrong+

Linked List Pattern Comparison

Pattern	Primary Use Case	Key Advantage
Fast & Slow Pointers	Cycle detection, Middle of list	O(1) Space optimization
Dummy Node	Merging lists, Deleting nodes	Removes head-null edge cases
In-Place Reversal	Reversing a list or sub-list	No extra memory allocation
Two Pointers (Offset)	N-th node from end	Finds target in a single pass
Recursive Merge	Merging sorted lists (small sizes)	Clean, intuitive code
Clone with Random Pointers	Deep copy with additional pointers	Uses hash map or interleaving for O(n)

Key takeaways

You now understand that Linked List problems are about pointer manipulation, not complex arithmetic.

You've implemented the two most vital patterns—Cycle Detection and Dummy Nodes—under the io.thecodeforge standards.

Mastering 'Fast & Slow' pointers is the single biggest unlock for passing FAANG-level linked list rounds.

Practice daily

the forge only works when it's hot 🔥

In-Place Reversal saves space but destroys original; clone if you need both.

Two pointers (offset) pattern finds N-th from end in one pass

always use a dummy node if removal is required.

Recursion is elegant but dangerous for large lists

know when to switch to iteration.

Common mistakes to avoid

5 patterns

Failing to update the 'current' pointer inside a loop

Symptom

Infinite loop or logic stall — the program keeps iterating over the same node or never advances.

Fix

Always move current = current.next at the end of the loop iteration. Double-check your loop condition to ensure advancement.

Accessing 'node.next.next' without checking if 'node.next' exists first

Symptom

NullPointerException when traversing or reversing a list with only one node or when reaching the end prematurely.

Fix

Always check if (node != null && node.next != null) before accessing node.next.next. Use a guard clause at the start of methods that rely on two-step traversal.

Losing the reference to the head of the list during a reversal

Symptom

After reversal, the list is lost or incorrect. The head pointer is pointing to an arbitrary node or null.

Fix

Always keep a prev reference (initially null) and a nextTemp before reassigning current.next. At the end, prev becomes the new head.

Using recursion on a very long linked list

Symptom

StackOverflowError when the list length exceeds the stack depth (typically a few thousand).

Fix

Prefer iterative solutions for any code that will run on production systems with potentially large data. If recursion is used, set a recursion limit or switch to iteration based on stack depth.

Forgetting to handle the case where n is larger than the list length in Nth-from-end problems

Symptom

NullPointerException or returning the head unchanged, causing incorrect removal.

Fix

Before the offset loop, check if the list length is less than n. If so, return null or throw an appropriate exception. In the code, verify first does not become null prematurely.

INTERVIEW PREP · PRACTICE MODE

Interview Questions on This Topic

Q01SENIOR

Explain how Floyd's cycle detection algorithm works. Code it and discuss...

Q02SENIOR

Merge two sorted linked lists. Compare iterative (dummy node) vs recursi...

Q03SENIOR

Given a linked list, how would you check if it's a palindrome without us...

Q04SENIOR

Explain how to clone a linked list with random pointers (each node has a...

Q01 of 04SENIOR

Explain how Floyd's cycle detection algorithm works. Code it and discuss space complexity.

ANSWER

Floyd's algorithm uses two pointers: slow moves one step at a time, fast moves two steps. If there is a cycle, the fast pointer will eventually lap the slow pointer and they will meet. This proves a cycle exists. Time complexity is O(n), space O(1). To find the start of the cycle, after they meet, move one pointer back to head and advance both at the same speed; the meeting point is the cycle start.

FAQ · 5 QUESTIONS

Frequently Asked Questions

When should I use a Dummy Node in a Linked List problem?

What is the time complexity of finding the N-th node from the end?

Is it better to solve Linked List problems recursively or iteratively?

How can I detect if a linked list has a cycle and find its starting point?

What is the trickiest linked list problem in interviews?

🔥

That's Coding Patterns. Mark it forged?

3 min read · try the examples if you haven't