Linked List Problems

Imagine you are running on a circular track with a friend. Your friend runs twice as fast as you. Even though you started together, they will eventually lap you and you will meet again! This is exactly how Floyd's Cycle Detection works. It is one of the most elegant algorithms in computer science, using only two pointers and O(1) extra space to detect if a linked list has a loop.

// Detect if linked list has a cycle
// Time: O(n), Space: O(1)
boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) {
        return false;
    }
    
    ListNode slow = head;
    ListNode fast = head;
    
    while (fast != null && fast.next != null) {
        slow = slow.next;         // Move 1 step
        fast = fast.next.next;    // Move 2 steps
        
        if (slow == fast) {
            return true;  // Cycle detected
        }
    }
    
    return false;  // No cycle (fast reached end)
}

// Find the start of the cycle
ListNode detectCycleStart(ListNode head) {
    if (head == null || head.next == null) {
        return null;
    }
    
    ListNode slow = head;
    ListNode fast = head;
    
    // Phase 1: Detect cycle
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        
        if (slow == fast) {
            break;  // Cycle found
        }
    }
    
    // No cycle
    if (fast == null || fast.next == null) {
        return null;
    }
    
    // Phase 2: Find start of cycle
    // Move slow back to head, keep fast at meeting point
    // Both move 1 step at a time - they meet at cycle start!
    slow = head;
    while (slow != fast) {
        slow = slow.next;
        fast = fast.next;
    }
    
    return slow;  // Start of cycle
}

LINKED LIST WITH CYCLE:

    1 → 2 → 3 → 4 → 5
                ↓   ↑
                6 → 7

PHASE 1: DETECTION (slow=1 step, fast=2 steps)
─────────────────────────────────────────────
Step 0: slow=1, fast=1
Step 1: slow=2, fast=3
Step 2: slow=3, fast=5
Step 3: slow=4, fast=7
Step 4: slow=5, fast=5  ← THEY MEET! Cycle exists.

PHASE 2: FIND CYCLE START
─────────────────────────────────────────────
Reset slow to head, both move 1 step:
  slow=1, fast=5 → slow=2, fast=6 → slow=3, fast=7
  → slow=4, fast=4  ← MEET AT CYCLE START (node 4)!

Think of merging sorted lists like shuffling two sorted decks of cards into one sorted deck. You always pick the smaller card from the top of either deck and place it in your result pile. This fundamental technique appears everywhere - from merge sort to database operations. Mastering this pattern opens doors to solving many related problems!

Iterative Approach - O(n + m) Time, O(1) Space

The iterative approach uses a dummy node to simplify edge cases. We compare nodes from both lists and always pick the smaller one, building our result list one node at a time.

ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    // Dummy node acts as a placeholder for the result list's head
    // This avoids special handling for the first node
    ListNode dummy = new ListNode(0);
    
    // curr pointer will build the result list
    ListNode curr = dummy;
}

Why use a dummy node? Without it, you would need special code to handle the very first node (since there is no "previous" node to attach to). The dummy node acts as a placeholder - we build the result after it, then return dummy.next to skip the placeholder. This trick eliminates messy if-else conditions and makes your code cleaner!

    // While both lists have nodes to compare
    while (l1 != null && l2 != null) {
        if (l1.val <= l2.val) {
            // l1's value is smaller, link it to result
            curr.next = l1;
            l1 = l1.next;  // Move l1 forward
        } else {
            // l2's value is smaller, link it to result
            curr.next = l2;
            l2 = l2.next;  // Move l2 forward
        }
        curr = curr.next;  // Move result pointer forward
    }

This is the heart of the algorithm. We compare the current nodes of both lists and pick the smaller one. Notice that we are not creating new nodes - we are reusing the existing nodes by changing their next pointers. This is why space complexity is O(1). Think of it like rearranging cards on a table rather than making copies of them!

    // One list is exhausted, attach the rest of the other list
    // No need to iterate - just link the remaining portion!
    curr.next = (l1 != null) ? l1 : l2;
    
    // Return the merged list (skip the dummy node)
    return dummy.next;
}

The cleanup step is simple but clever. When the while loop ends, one list is empty but the other might still have nodes. Since both lists were already sorted, the remaining nodes are guaranteed to be larger than everything we have added so far. We just attach them directly with one pointer assignment - no need to iterate through them one by one!

Recursive Approach - O(n + m) Time, O(n + m) Space

The recursive approach is more elegant but uses O(n + m) stack space due to recursion. Each call handles one node and delegates the rest to the next recursive call.

ListNode mergeTwoListsRecursive(ListNode l1, ListNode l2) {
    // Base cases: if one list is empty, return the other
    if (l1 == null) return l2;
    if (l2 == null) return l1;
    
    // Pick the smaller node and recursively merge the rest
    if (l1.val <= l2.val) {
        // l1 is smaller, so l1.next should point to the merge of (l1.next, l2)
        l1.next = mergeTwoListsRecursive(l1.next, l2);
        return l1;  // l1 becomes the head of this merged portion
    } else {
        // l2 is smaller, so l2.next should point to the merge of (l1, l2.next)
        l2.next = mergeTwoListsRecursive(l1, l2.next);
        return l2;  // l2 becomes the head of this merged portion
    }
}

The recursive approach is elegant but has a trade-off. Each recursive call adds a frame to the call stack, using O(n + m) extra memory. For a list with 10,000 nodes, that is 10,000 stack frames! If the list is very long, you might get a StackOverflowError. The iterative approach above uses only O(1) space, making it safer for large inputs. In interviews, mention this trade-off to show you understand both solutions deeply.

Advanced: Merge K Sorted Lists - O(N log k) Time

When you have K sorted lists (not just 2), comparing all K heads each time would be O(K) per node. Using a min-heap (priority queue) reduces this to O(log K) per node, giving O(N log K) total where N is the total number of nodes.

ListNode mergeKLists(ListNode[] lists) {
    // Min-heap ordered by node value
    PriorityQueue pq = new PriorityQueue<>(
        (a, b) -> a.val - b.val  // Comparator: smaller values first
    );
    
    // Add the head of each non-empty list to the heap
    for (ListNode list : lists) {
        if (list != null) {
            pq.offer(list);
        }
    }
}

Why use a heap (PriorityQueue)? If we had to compare all K list heads manually each time, that would be O(K) per node - too slow! A min-heap automatically keeps the smallest element at the top, and adding/removing takes only O(log K) time. Since the heap only holds one node from each list at a time (at most K nodes), operations stay fast even with many lists.

    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;
    
    while (!pq.isEmpty()) {
        // Get the smallest node from the heap
        ListNode node = pq.poll();
        
        // Add it to our result
        curr.next = node;
        curr = curr.next;
        
        // If this node has a next, add it to the heap
        if (node.next != null) {
            pq.offer(node.next);
        }
    }
    
    return dummy.next;
}

Understanding the time complexity: Every single node across all K lists will be added to the heap once and removed once. If there are N total nodes, that is 2N heap operations. Each heap operation (offer/poll) takes O(log K) time because the heap has at most K elements. So total time = N nodes x O(log K) per operation = O(N log K). This is much better than the naive O(N x K) approach!

  List 1:  [1] ──▶ [3] ──▶ [5] ──▶ null
  List 2:  [2] ──▶ [4] ──▶ [6] ──▶ null

Compare 1 vs 2 → Take 1
  dummy → [1]
  L1 at 3, L2 at 2

Compare 3 vs 2 → Take 2
  dummy → [1] → [2]
  L1 at 3, L2 at 4

Compare 3 vs 4 → Take 3
  dummy → [1] → [2] → [3]
  L1 at 5, L2 at 4

Compare 5 vs 4 → Take 4
  dummy → [1] → [2] → [3] → [4]
  L1 at 5, L2 at 6

  dummy ──▶ [1] ──▶ [2] ──▶ [3] ──▶ [4] ──▶ [5] ──▶ [6] ──▶ null
               ▲
          Return dummy.next!                    ✓ Perfectly Merged!

Here is a puzzle: How do you find something that is "5 steps from the end" when you do not know where the end is? The naive approach would traverse twice - once to find the length, once to reach the target. But there is a clever trick using two pointers with a fixed gap between them. When the leading pointer hits the end, the trailing pointer is exactly where we need it. One pass, constant space!

Remove Nth Node - O(n) Time, O(1) Space

The key insight is maintaining a fixed gap between two pointers. When the leading pointer reaches the end, the trailing pointer is exactly where we need to perform the deletion.

ListNode removeNthFromEnd(ListNode head, int n) {
    // Dummy node helps when removing head
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    
    ListNode slow = dummy;
    ListNode fast = dummy;
}

Why start both at dummy? Starting at the dummy node (not head) means when we finish, slow will be at the node BEFORE the one we want to delete. This is crucial because to delete a node in a linked list, we need access to the previous node to change its next pointer.

    // Move fast n+1 steps ahead
    for (int i = 0; i <= n; i++) {
        fast = fast.next;
    }

Why n+1 steps (not n)? We move fast n+1 steps to create a gap of n+1 nodes. This way, when fast reaches null (end of list), slow will be exactly one node BEFORE the target. Remember: to delete a node, we need its predecessor!

    // Move both until fast reaches end
    while (fast != null) {
        slow = slow.next;
        fast = fast.next;
    }

The magic of synchronized movement. Both pointers move at the same speed, maintaining the n+1 gap. When fast hits null, slow has traveled (length - n - 1) steps from dummy, landing exactly at the predecessor of the nth node from end.

    // slow is now at node before the one to remove
    slow.next = slow.next.next;
    
    return dummy.next;
}

The deletion is just one line! Since slow points to the predecessor, we simply skip over the target node by pointing slow.next to slow.next.next. We return dummy.next (not head) because the original head might have been the deleted node!

Bonus: Get Nth Node (Without Deleting)

Sometimes you just need to find the nth node from end without deleting it. The approach is similar but simpler - we only need n steps gap (not n+1) since we want the actual node, not its predecessor.

ListNode getNthFromEnd(ListNode head, int n) {
    ListNode slow = head;
    ListNode fast = head;
    
    // Move fast n steps ahead (not n+1!)
    for (int i = 0; i < n; i++) {
        if (fast == null) return null;  // List too short
        fast = fast.next;
    }
}

Notice the difference: Here we move fast only n steps (not n+1), and we start both pointers at head (not dummy). This is because we want to land ON the target node, not before it. The null check handles the edge case where n is larger than the list length.

    // Move both until fast reaches end
    while (fast != null) {
        slow = slow.next;
        fast = fast.next;
    }
    
    return slow;  // nth node from end
}

Same synchronized movement, different result. With an n-step gap (instead of n+1), slow lands directly on the nth node from end. This is useful for problems like "find the middle" or "find kth from end" where you need to access the node's value.

  dummy ──▶ [1] ──▶ [2] ──▶ [3] ──▶ [4] ──▶ [5] ──▶ null
                                        ▲
                                   Target: 2nd from end

Move fast (n+1 = 3) steps ahead

dummy ──▶ [1] ──▶ [2] ──▶ [3] ──▶ [4] ──▶ [5]
  ▲                   ▲
 slow               fast

Gap = 3 nodes (n+1)

Both move until fast = null

dummy ──▶ [1] ──▶ [2] ──▶ [3] ──▶ [4] ──▶ [5] ──▶ null
                        ▲                   ▲
                       slow                fast

slow is BEFORE target!

  slow.next = slow.next.next  // Skip node 4!

  dummy ──▶ [1] ──▶ [2] ──▶ [3] ─────────▶ [5] ──▶ null
                                  ✗
                             [4] removed!

  ✓ Result: 1 → 2 → 3 → 5

Picture two roads that merge into one highway. Two cars start on different roads - how do they find where the roads meet? The beautiful solution: each car drives its road, then switches to the other road. They will meet at the intersection because they travel equal total distances! This problem teaches us that sometimes the most elegant solutions come from thinking about the problem differently.

Elegant Approach - O(n + m) Time, O(1) Space

This is one of the most beautiful algorithms in linked list problems. Instead of calculating lengths, we use a clever trick: make both pointers travel the same total distance by switching lists!

ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;
    
    ListNode a = headA;
    ListNode b = headB;
}

Simple setup. We create two pointers, one starting at each list's head. The null check handles the edge case where either list is empty (no intersection possible).

    // When a reaches end, redirect to headB
    // When b reaches end, redirect to headA
    // They will meet at intersection or both become null
    while (a != b) {
        a = (a == null) ? headB : a.next;
        b = (b == null) ? headA : b.next;
    }

The magic trick! When pointer 'a' finishes list A, it jumps to the head of list B. Similarly, 'b' jumps to head of A when it finishes B. This means both pointers travel exactly (lenA + lenB) nodes total. If there is an intersection, they will arrive at it simultaneously because they have traveled the same distance!

    return a;  // Intersection node or null
}

Why does this work? If lists intersect, both pointers meet at the intersection node. If they do not intersect, both pointers become null at the same time (after traveling lenA + lenB each), so we return null. Beautiful!

Alternative: Length-Based Approach

A more intuitive approach: calculate lengths first, align the starting points, then walk together until we find the intersection.

ListNode getIntersectionV2(ListNode headA, ListNode headB) {
    int lenA = getLength(headA);
    int lenB = getLength(headB);
}

First pass: count nodes. We need to know how long each list is. This requires traversing both lists once, which is O(n + m) time.

    // Advance the longer list to align starting points
    while (lenA > lenB) {
        headA = headA.next;
        lenA--;
    }
    while (lenB > lenA) {
        headB = headB.next;
        lenB--;
    }

Align the pointers. If list A has 5 nodes and list B has 3 nodes, we advance A by 2 nodes first. Now both pointers are the same distance from the end (and from the potential intersection point). Think of it like two runners starting a race at different points - we move the ahead runner back so they start together.

    // Move together until intersection (or both null)
    while (headA != headB) {
        headA = headA.next;
        headB = headB.next;
    }
    
    return headA;  // Intersection or null
}

Walk in sync. Now that both pointers are aligned (same distance from intersection), we move them together one step at a time. When they meet, we have found the intersection! If they both become null, there is no intersection.

int getLength(ListNode head) {
    int len = 0;
    while (head != null) {
        len++;
        head = head.next;
    }
    return len;
}

Helper function. A simple traversal to count nodes. Note that we use a local copy of head, so the original pointer is not modified. This is a common helper for many linked list problems.

  List A:  [a1] ──▶ [a2] ──╮
                              ╰──▶ [c1] ──▶ [c2] ──▶ [c3] ──▶ null
  List B:  [b1] ──▶ [b2] ──▶ [b3] ──╯
                              ▲
                        Intersection at c1

Traverse List A first:
  a1 → a2 → c1 → c2 → c3 → null

Switch to List B:
  b1 → b2 → b3 → c1 ✓ STOP!

Total: 2 + 3 + 3 + 1 = 9 steps

Traverse List B first:
  b1 → b2 → b3 → c1 → c2 → c3 → null

Switch to List A:
  a1 → a2 → c1 ✓ STOP!

Total: 3 + 3 + 2 + 1 = 9 steps

  Both pointers travel lenA + lenB = 5 + 6 = 11 nodes total

  After 9 steps each:  Pointer A at [c1]  ←─┬─→  Pointer B at [c1]
                                         │
                                   ✓ INTERSECTION FOUND!

A palindrome reads the same forwards and backwards - like "racecar" or "12321". Checking this in a string is easy (just compare first and last characters moving inward), but linked lists only go forward! The trick is to find the middle, reverse the second half, then compare. This combines three patterns you have learned: slow/fast pointers, reversal, and two-pointer comparison.

Check Palindrome - O(n) Time, O(1) Space

This algorithm combines three patterns you have already learned: slow/fast pointers to find the middle, list reversal, and two-pointer comparison. The key insight is that we only need to reverse half the list!

boolean isPalindrome(ListNode head) {
    // Edge cases: empty list or single node is always a palindrome
    if (head == null || head.next == null) return true;
    
    // Find the middle using slow/fast pointers
    ListNode slow = head;
    ListNode fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
}

Finding the middle is the first step. We use the slow/fast pointer technique where fast moves twice as fast as slow. When fast reaches the end, slow is at the middle. For odd-length lists (like 1-2-3-2-1), slow lands on the center node (3). For even-length lists (like 1-2-2-1), slow lands on the last node of the first half (the first 2).

    // Reverse the second half of the list
    ListNode secondHalf = reverse(slow.next);
    
    // Save reference for restoration later
    ListNode secondHalfCopy = secondHalf;

Reverse only the second half. We call our reverse helper on slow.next (the node after middle). This gives us the second half in reverse order. We save a copy of this pointer because we will move secondHalf during comparison and need the original reference to restore the list later.

    // Compare first half with reversed second half
    ListNode firstHalf = head;
    boolean isPalin = true;
    
    while (secondHalf != null) {
        if (firstHalf.val != secondHalf.val) {
            isPalin = false;
            break;
        }
        firstHalf = firstHalf.next;
        secondHalf = secondHalf.next;
    }

Compare values node by node. We walk through the first half from the beginning and the reversed second half simultaneously. If any values differ, it is not a palindrome. We use a boolean flag instead of returning immediately because we want to restore the list structure before returning (good practice to not leave data structures in a modified state).

    // Restore the list to original structure (optional but good practice)
    slow.next = reverse(secondHalfCopy);
    
    return isPalin;
}

Restore the original structure. By reversing the second half again, we put the list back to its original state. This is optional but considered good practice - the caller might not expect the list to be modified. In interviews, mention this to show you think about side effects!

Helper: Reverse a Linked List

This is the standard iterative reversal that you should memorize. It uses three pointers and runs in O(n) time with O(1) space.

private ListNode reverse(ListNode head) {
    ListNode prev = null;
    
    while (head != null) {
        ListNode next = head.next;  // Save next node
        head.next = prev;           // Reverse the link
        prev = head;                // Move prev forward
        head = next;                // Move head forward
    }
    
    return prev;  // prev is now the new head
}

The classic reversal pattern. Remember the order: save next, reverse link, advance prev, advance head. The key is saving head.next BEFORE changing it, otherwise you lose the reference to the rest of the list. When the loop ends, prev points to what was the last node - now the new head of the reversed list.

  [1] ──▶ [2] ──▶ [3] ──▶ [2] ──▶ [1] ──▶ null
                      ▲
                   middle

slow moves 1 step, fast moves 2 steps

Start: S,F at [1]
Step 1: S→[2], F→[3]
Step 2: S→[3], F→[1] (end!)

slow is at middle node [3]

Reverse everything after middle:

Before: [3] → [2] → [1] → null
After:  [3]   [1] → [2] → null

First half:  1 → 2 → 3
Second half: 1 → 2 (reversed!)

  First half:     [1] ──▶ [2] ──▶ [3]
                    ║       ║
                    ▼       ▼
  Second half:    [1] ──▶ [2]

  Compare: 1 == 1 ✓   2 == 2 ✓   IT'S A PALINDROME!

Imagine folding a linked list in half and interleaving the two halves like shuffling cards. This problem asks you to transform a list from its original order to an alternating pattern that picks from both ends. It combines all three core patterns: find middle, reverse, and merge.

Reorder List - O(n) Time, O(1) Space

This problem is solved in three steps: find the middle, reverse the second half, then interleave the two halves. Each step uses a pattern you have already learned!

void reorderList(ListNode head) {
    // Edge cases: nothing to reorder
    if (head == null || head.next == null) return;
    
    // Find the middle using slow/fast pointers
    ListNode slow = head, fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
}

Finding the middle splits the list into two halves. We use the familiar slow/fast pointer technique. When the loop ends, slow is at the middle node. For a list 1-2-3-4-5, slow will be at node 3. For a list 1-2-3-4, slow will be at node 2. This positioning ensures the first half is equal or one node longer than the second half.

    // Reverse the second half of the list
    ListNode second = reverse(slow.next);
    
    // Cut the list into two separate lists
    slow.next = null;

Reverse and disconnect. We reverse everything after the middle node, so 4-5 becomes 5-4. Then we set slow.next = null to cut the list into two separate lists. This is important because otherwise we would have a cycle when we start interleaving! Now we have: first = 1-2-3-null and second = 5-4-null.

    // Interleave: merge first and second half alternately
    ListNode first = head;
    
    while (second != null) {
        // Save next pointers before we modify them
        ListNode temp1 = first.next;
        ListNode temp2 = second.next;
        
        // Weave second node after first node
        first.next = second;
        second.next = temp1;
        
        // Move to next pair
        first = temp1;
        second = temp2;
    }
}

The interleaving is like shuffling cards. We take one node from the first half, then one from the second half, alternating until done. The key is saving both temp1 and temp2 before modifying any pointers. After each iteration: first.next points to a node from second, and that node points to what was first.next. We stop when second becomes null (the second half is always equal or shorter).

Bonus: Add Two Numbers

A classic interview problem where two numbers are represented as linked lists with digits in reverse order (123 is stored as 3-2-1). We add them digit by digit, handling carries just like grade-school addition.

ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;
    int carry = 0;
}

Setup with dummy node and carry. The dummy node simplifies building the result list. The carry variable holds any overflow from the previous digit addition (just like when 7+5=12, we write 2 and carry the 1).

    while (l1 != null || l2 != null || carry != 0) {
        int sum = carry;
        
        if (l1 != null) {
            sum += l1.val;
            l1 = l1.next;
        }
        if (l2 != null) {
            sum += l2.val;
            l2 = l2.next;
        }
        
        carry = sum / 10;
        curr.next = new ListNode(sum % 10);
        curr = curr.next;
    }
    
    return dummy.next;
}

Process digit by digit. The loop continues while there are digits in either list OR there is a remaining carry. We add the carry first, then add digits from l1 and l2 if they exist. The new digit is sum % 10 (the ones place), and the new carry is sum / 10 (the tens place). For example: 7+8+1(carry)=16, so new digit is 6, new carry is 1.

  [1] ──▶ [2] ──▶ [3] ──▶ [4] ──▶ [5] ──▶ null
   L₀      L₁      L₂      L₃      L₄

First half:
  [1] ──▶ [2] ──▶ [3] ──▶ null

Second half:
  [4] ──▶ [5] ──▶ null

Before: [4] ──▶ [5]
              ↓ reverse
After:  [5] ──▶ [4] ──▶ null
         L₄      L₃

  [1] ──▶ [5] ──▶ [2] ──▶ [4] ──▶ [3] ──▶ null
   L₀      L₄      L₁      L₃      L₂

  Pattern: front → back → front → back → front  ✓ Perfect!

Even experienced developers fall into these traps when solving linked list problems. Learn to recognize and avoid them to write bug-free code in interviews!

curr.next = prev;
curr = curr.next;

next = curr.next;
curr.next = prev;
curr = next;

while (fast.next != null)

while (fast != null 
    && fast.next != null)

if (head.val == target)
  return head.next;
// Different logic...

dummy.next = head;
// Same logic for all!
return dummy.next;

public ListNode solve(ListNode head) {
    if (head == null) return null;           // Edge case 1: Empty list
    if (head.next == null) return head;      // Edge case 2: Single node
    // Now safe to access head.next, use two pointers, etc.
}

When you see a linked list problem, use this guide to quickly identify which pattern to apply. Most problems are variations of these core patterns!

Watch the tortoise (slow) and hare (fast) race through a linked list with a cycle. See how they eventually meet, proving the cycle exists!

Click "Start Demo" to watch Floyd's Algorithm in action!

List with cycle:
[1] → [2] → [3] → [4] → [5]
                  ↓       ↑
                  [6] → [7]

Slow (🐢) moves 1 step per iteration
Fast (🐇) moves 2 steps per iteration
                    

Understanding complexity is crucial for interviews. Here is a quick reference for all the problems we covered. Notice how most achieve O(n) time and O(1) space - that is the beauty of linked list algorithms!

Copy these templates into your interviews as starting points. They handle common patterns and edge cases, so you can focus on the problem-specific logic.

ListNode slow = head, fast = head;

// For finding middle (second middle for even):
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
}
// slow is now at middle

// For cycle detection:
while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
    if (slow == fast) return true;
}
return false;

// Use when head might change
ListNode dummy = new ListNode(0);
dummy.next = head;

ListNode curr = dummy;
while (curr.next != null) {
    // Process curr.next
    // curr.next = curr.next.next to delete
    curr = curr.next;
}

return dummy.next; // New head

ListNode reverse(ListNode head) {
    ListNode prev = null;
    ListNode curr = head;
    
    while (curr != null) {
        ListNode next = curr.next; // Save
        curr.next = prev;          // Reverse
        prev = curr;               // Advance
        curr = next;
    }
    
    return prev; // New head
}

// Remove nth from end
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode fast = dummy, slow = dummy;

// Move fast n+1 ahead
for (int i = 0; i <= n; i++) {
    fast = fast.next;
}

// Move both until fast = null
while (fast != null) {
    slow = slow.next;
    fast = fast.next;
}

slow.next = slow.next.next;
return dummy.next;

Use this checklist during your interview to make sure you cover all bases. Interviewers love candidates who think systematically!