Chapter 28 of 65

Linked List Problems (Reversal & Fast/Slow Pointers)

On this page

In the last three chapters you learned how singly, doubly and circular linked lists are built: nodes, head, next, insertion and deletion.

Interviewers rarely ask you to just "insert a node". Instead they ask questions like:

  • "Reverse this linked list."

  • "Find the middle node in one pass."

  • "Does this list have a cycle? Where does the cycle start?"

  • "Remove the 2nd node from the end."

  • "Is this list a palindrome, using O(1) extra space?"

The good news is that almost all of these are solved with just two tools:

  1. Pointer reversal: changing next references carefully, one node at a time.

  2. Fast and slow pointers: two references that move through the list at different speeds (or with a fixed gap).

Plus one small trick, the dummy node, that removes most special cases. Let's learn all three.

The Setup We Will Use

All programs in this chapter use the same Node class from the Linked List chapter, plus two small helpers: build creates a list from values, and print shows it.

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
    }
}
static Node build(int... values) {
    Node dummy = new Node(0);
    Node tail = dummy;
    for (int v : values) {
        tail.next = new Node(v);
        tail = tail.next;
    }
    return dummy.next;
}

static void print(Node head) {
    StringBuilder sb = new StringBuilder();
    for (Node cur = head; cur != null; cur = cur.next) {
        sb.append(cur.data).append(" -> ");
    }
    System.out.println(sb.append("null"));
}

Notice that build already uses a dummy node. We'll explain why later in this chapter.

Problem 1: Reverse a Linked List

Problem: Given the head of a singly linked list, reverse it and return the new head.

Input:  1 → 2 → 3 → 4 → 5 → null
Output: 5 → 4 → 3 → 2 → 1 → null

With an array, you would swap the first and last elements and move inwards. With a singly linked list, you cannot jump to the last node, and you cannot walk backwards. So instead of moving values, we turn every arrow around.

Before:  1 → 2 → 3 → null
After:   null ← 1 ← 2 ← 3

The Three-Pointer Idea

We walk through the list with three references:

  • prev: the part we have already reversed (starts as null).

  • curr: the node we are reversing now (starts as head).

  • next: a temporary reference that remembers the rest of the list.

For each node we do four steps, in this order:

1. next = curr.next     save the rest of the list
2. curr.next = prev     turn the arrow around
3. prev = curr          prev moves one step
4. curr = next          curr moves one step

Step 1 is the important one. As soon as we do curr.next = prev, the link to the rest of the list is gone. If we had not saved it in next, we would lose the remaining nodes forever.

Step-by-Step Trace

Let's reverse 1 → 2 → 3 → null.

Start:      prev = null, curr = 1
            null    1 → 2 → 3 → null

Iteration 1: next = 2, 1.next = null, prev = 1, curr = 2
            null ← 1    2 → 3 → null

Iteration 2: next = 3, 2.next = 1, prev = 2, curr = 3
            null ← 1 ← 2    3 → null

Iteration 3: next = null, 3.next = 2, prev = 3, curr = null
            null ← 1 ← 2 ← 3

curr is null → stop. Return prev (3), the new head.

Recursive Reversal

Reversal can also be written recursively (see the Recursion chapter). The idea is:

  • Base case: an empty list or a single node is already reversed.

  • Recursive step: reverse everything after head. Then the node right after head (which is now the tail of the reversed part) should point back to head, and head should point to null.

Trace for 1 → 2 → 3:

reverseRecursive(1)
  reverseRecursive(2)
    reverseRecursive(3)  → base case, returns 3

  back in call for 2:  2.next is 3
      3.next = 2 ; 2.next = null      list part: 3 → 2 → null
      return 3

back in call for 1:  1.next is still 2
      2.next = 1 ; 1.next = null      list: 3 → 2 → 1 → null
      return 3

The new head (3) is found at the bottom of the recursion and simply passed back up unchanged.

Reversal in Java

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
    }
}

class Main {

    static Node build(int... values) {
        Node dummy = new Node(0);
        Node tail = dummy;
        for (int v : values) {
            tail.next = new Node(v);
            tail = tail.next;
        }
        return dummy.next;
    }

    static void print(Node head) {
        StringBuilder sb = new StringBuilder();
        for (Node cur = head; cur != null; cur = cur.next) {
            sb.append(cur.data).append(" -> ");
        }
        System.out.println(sb.append("null"));
    }

    // Iterative reversal: O(n) time, O(1) extra space
    static Node reverse(Node head) {
        Node prev = null;
        Node curr = head;

        while (curr != null) {
            Node next = curr.next;   // 1. save the rest of the list
            curr.next = prev;        // 2. reverse the link
            prev = curr;             // 3. move prev forward
            curr = next;             // 4. move curr forward
        }

        return prev;                 // prev is the new head
    }

    // Recursive reversal: O(n) time, O(n) call-stack space
    static Node reverseRecursive(Node head) {
        if (head == null || head.next == null) {
            return head;             // empty list or last node
        }

        Node newHead = reverseRecursive(head.next);

        head.next.next = head;       // the node after head now points back to head
        head.next = null;            // head becomes the tail

        return newHead;
    }

    public static void main(String[] args) {

        Node head = build(1, 2, 3, 4, 5);
        System.out.print("Original:            ");
        print(head);

        head = reverse(head);
        System.out.print("Reversed:            ");
        print(head);

        head = reverseRecursive(head);
        System.out.print("Reversed again:      ");
        print(head);

        System.out.print("Single node:         ");
        print(reverse(build(7)));

        System.out.print("Empty list:          ");
        print(reverse(null));
    }
}

Output:

Original:            1 -> 2 -> 3 -> 4 -> 5 -> null
Reversed:            5 -> 4 -> 3 -> 2 -> 1 -> null
Reversed again:      1 -> 2 -> 3 -> 4 -> 5 -> null
Single node:         7 -> null
Empty list:          null

Always test the two edge cases at the bottom (one node, empty list). The iterative version handles both without any extra if.

Version

Time

Extra space

Notes

Iterative

O(n)

O(1)

Preferred in interviews and production

Recursive

O(n)

O(n) (call stack)

Elegant, but a very long list can cause StackOverflowError

Problem 2: Reverse Part of a List

Problem: Reverse only the nodes from position left to position right (1-based).

Input:  1 → 2 → 3 → 4 → 5,   left = 2, right = 4
Output: 1 → 4 → 3 → 2 → 5

We reuse the same reversal loop, but only for right - left + 1 nodes. Then we reconnect the reversed part to the nodes on both sides.

before = node at position left - 1     (here: 1)

Reverse 2 → 3 → 4 :
    prev = 4  (new head of the part)
    curr = 5  (first node after the part)
    node 2 is now the tail of the part

Reconnect:
    2.next = 5         (before.next.next = curr)
    1.next = 4         (before.next = prev)

Result: 1 → 4 → 3 → 2 → 5

What if left = 1? Then there is no node before the part. Instead of writing special code for that case, we put a dummy node in front of the head. That brings us to the next idea.

The Dummy Node Trick

A dummy node (also called a sentinel) is a fake node placed before the real head:

dummy → 1 → 2 → 3 → null

Its value does not matter. It guarantees that every real node has a node before it, even the head. So "delete the head" or "insert before the head" become ordinary operations. At the end, the real head is simply dummy.next.

Use a dummy node whenever the head itself might change: deleting nodes, reversing a part that may start at the head, or building a new list (such as merging two sorted lists).

Merge two sorted lists is a classic example (you saw merging of arrays in the Merge Sort chapter). We keep a tail pointer and always attach the smaller front node. The program below contains both reverseBetween from Problem 2 and merge:

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
    }
}

class Main {

    static Node build(int... values) {
        Node dummy = new Node(0);
        Node tail = dummy;
        for (int v : values) {
            tail.next = new Node(v);
            tail = tail.next;
        }
        return dummy.next;
    }

    static void print(Node head) {
        StringBuilder sb = new StringBuilder();
        for (Node cur = head; cur != null; cur = cur.next) {
            sb.append(cur.data).append(" -> ");
        }
        System.out.println(sb.append("null"));
    }

    // Reverse only the nodes from position left to right (1-based)
    static Node reverseBetween(Node head, int left, int right) {
        Node dummy = new Node(0);
        dummy.next = head;

        Node before = dummy;
        for (int i = 1; i < left; i++) {
            before = before.next;          // node just before position left
        }

        Node prev = null;
        Node curr = before.next;
        for (int i = left; i <= right; i++) {
            Node next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }

        // before.next is the old first node of the part, now its last node
        before.next.next = curr;           // connect the part's tail to the rest
        before.next = prev;                // connect the front to the part's new head

        return dummy.next;
    }

    // Merge two sorted lists using a dummy node
    static Node merge(Node a, Node b) {
        Node dummy = new Node(0);
        Node tail = dummy;

        while (a != null && b != null) {
            if (a.data <= b.data) {
                tail.next = a;
                a = a.next;
            } else {
                tail.next = b;
                b = b.next;
            }
            tail = tail.next;
        }
        tail.next = (a != null) ? a : b;   // attach whatever is left

        return dummy.next;
    }

    public static void main(String[] args) {

        System.out.print("Reverse positions 2..4: ");
        print(reverseBetween(build(1, 2, 3, 4, 5), 2, 4));

        System.out.print("Reverse positions 1..5: ");
        print(reverseBetween(build(1, 2, 3, 4, 5), 1, 5));

        System.out.print("Merged: ");
        print(merge(build(1, 4, 7), build(2, 3, 8, 9)));
    }
}

Output:

Reverse positions 2..4: 1 -> 4 -> 3 -> 2 -> 5 -> null
Reverse positions 1..5: 5 -> 4 -> 3 -> 2 -> 1 -> null
Merged: 1 -> 2 -> 3 -> 4 -> 7 -> 8 -> 9 -> null

The second line reverses from position 1, which changes the head. Thanks to the dummy node, the same code handles it. The merge runs in O(n + m) time and O(1) extra space, because it reuses the existing nodes instead of creating new ones.

Fast and Slow Pointers

In the Two Pointers chapter, you used slow and fast indexes on arrays. On linked lists, the same idea becomes even more powerful, because we cannot use indexes or know the length in advance.

Fast and slow pointers (also called the tortoise and hare technique): two references start at the head; the slow one moves 1 node per step and the fast one moves 2 nodes per step. Because their speeds differ, their positions reveal facts about the list's structure.

The basic loop always looks like this:

Node slow = head;
Node fast = head;

while (fast != null && fast.next != null) {
    slow = slow.next;          // 1 step
    fast = fast.next.next;     // 2 steps
}

The condition fast != null && fast.next != null is essential. Since fast jumps two nodes, we must check both before using fast.next.next, otherwise we get a NullPointerException.

Problem 3: Find the Middle Node

The naive way is two passes: count the nodes, then walk n / 2 steps. With fast and slow pointers we need only one pass.

When fast reaches the end, it has travelled twice as far as slow, so slow is in the middle.

Odd length (1 → 2 → 3 → 4 → 5):

Step 0:  slow = 1, fast = 1
Step 1:  slow = 2, fast = 3
Step 2:  slow = 3, fast = 5
fast.next is null → stop.  Middle = 3

Even length (1 → 2 → 3 → 4 → 5 → 6):

Step 0:  slow = 1, fast = 1
Step 1:  slow = 2, fast = 3
Step 2:  slow = 3, fast = 5
Step 3:  slow = 4, fast = null   (5 → 6 → null)
fast is null → stop.  Middle = 4

For an even length there are two middle nodes (3 and 4). This loop returns the second middle. If a problem wants the first middle (for example, to split a list into two halves for merge sort), change the condition:

// First middle (head must not be null)
while (fast.next != null && fast.next.next != null) {
    slow = slow.next;
    fast = fast.next.next;
}

For 1 → 2 → 3 → 4 → 5 → 6 this stops with slow = 3; for odd lengths both versions give the same answer.

Problem 4: Detect a Cycle (Floyd's Algorithm)

A linked list has a cycle if some node's next points back to an earlier node. Then a normal traversal never reaches null and loops forever.

1 → 2 → 3 → 4 → 5 → 6
        ↑               │
        └───────────────┘      (6.next = 3)

This is different from a circular linked list, where the last node deliberately points to the head. Here the cycle is usually a bug or a puzzle, and it may start anywhere.

Floyd's cycle detection uses the same slow/fast loop:

  • If there is no cycle, fast reaches null and we return false.

  • If there is a cycle, both pointers eventually go round it, and fast catches up with slow. When slow == fast (the same node object), we return true.

static boolean hasCycle(Node head) {
    Node slow = head;
    Node fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            return true;
        }
    }
    return false;
}

Why Can't Fast Jump Over Slow?

Once both pointers are inside the cycle, think of the distance from fast forward to slow. In each step, slow moves 1 ahead and fast moves 2 ahead, so the gap shrinks by exactly 1:

gap: 3 → 2 → 1 → 0   (they meet)

A gap that shrinks by 1 every step must hit 0 exactly; it cannot skip from 1 to -1. And since the gap is less than the cycle length when slow enters the cycle, they meet before slow finishes one full loop. So the algorithm takes O(n) time and only O(1) extra space.

Let's trace the list above:

Step 0:  slow = 1, fast = 1
Step 1:  slow = 2, fast = 3
Step 2:  slow = 3, fast = 5
Step 3:  slow = 4, fast = 3     (5 → 6 → 3)
Step 4:  slow = 5, fast = 5     → they meet at node 5. Cycle!

A simpler idea is to store every visited node in a set and stop when you see a node again. That also works in O(n) time, but needs O(n) extra space. (You will learn about HashSet later.) Floyd's algorithm is the answer interviewers expect because it uses O(1) space.

Problem 5: Find Where the Cycle Starts

This is the famous follow-up. After slow and fast meet:

  1. Put a new pointer p at the head.

  2. Move p and slow one step at a time.

  3. The node where they meet is the start of the cycle.

Why Does This Work?

Let:

  • a = number of steps from the head to the cycle start

  • b = number of steps from the cycle start to the meeting point (inside the cycle)

  • c = length of the cycle

head ──a steps──→ start ──b steps──→ meeting point
                    ↑                      │
                    └──── c - b steps ─────┘

When they meet:

slow has walked:  a + b
fast has walked:  2(a + b)            (twice as fast)

fast also equals slow's distance plus some full loops:
    2(a + b) = a + b + k·c            (k ≥ 1)
      a + b  = k·c
          a  = k·c - b
          a  = (k - 1)·c + (c - b)

The last line says: walking a steps from the meeting point is the same as walking c - b steps (which reaches the cycle start) plus some whole loops (which come back to the same place). So a pointer starting at the head and a pointer starting at the meeting point, both moving 1 step at a time, arrive at the cycle start at the same time.

Check with our example: head is 1, cycle start is 3, so a = 2. The cycle is 3 → 4 → 5 → 6 → 3, so c = 4. They met at node 5, so b = 2. Then a + b = 4 = 1 · c with k = 1, and c - b = 2 = a. Phase 2:

p = 1, slow = 5
p = 2, slow = 6
p = 3, slow = 3   → cycle starts at node 3
static Node cycleStart(Node head) {
    Node slow = head;
    Node fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            Node p = head;          // phase 2
            while (p != slow) {
                p = p.next;
                slow = slow.next;
            }
            return p;
        }
    }
    return null;
}

Cycle length: after the meeting, keep one pointer fixed and walk the other around the cycle until it comes back, counting the steps. For our example the answer is 4.

Problem 6: Remove the N-th Node from the End

This uses two pointers moving at the same speed but with a fixed gap between them.

The idea: move fast ahead by n nodes first. Then move both together. When fast reaches the last node, slow is exactly n nodes behind it, which is just before the node we want to delete.

We start both at a dummy node, so deleting the head works too.

List: dummy → 10 → 20 → 30 → 40 → 50,   n = 2  (delete 40)

Move fast 2 steps:           slow = dummy, fast = 20
Move both until fast.next == null:
                             slow = 10,    fast = 30
                             slow = 20,    fast = 40
                             slow = 30,    fast = 50   (fast.next is null, stop)
slow.next = slow.next.next   → 30 now points to 50

Result: 10 → 20 → 30 → 50

With n = 5, fast reaches 50 immediately, slow stays at the dummy, and the head (10) is removed. No special case needed.

static Node removeNthFromEnd(Node head, int n) {
    Node dummy = new Node(0);
    dummy.next = head;
    Node fast = dummy;
    Node slow = dummy;

    for (int i = 0; i < n; i++) {   // create a gap of n nodes
        fast = fast.next;
    }
    while (fast.next != null) {     // move both until fast is at the last node
        fast = fast.next;
        slow = slow.next;
    }
    slow.next = slow.next.next;     // slow is just before the node to delete
    return dummy.next;
}

This assumes 1 ≤ n ≤ length, as the problem usually guarantees. It finishes in a single pass.

Problem 7: Palindrome Linked List

Problem: Check whether a list reads the same forwards and backwards, using O(1) extra space.

1 → 2 → 3 → 2 → 1   → true
1 → 2 → 2 → 1       → true
1 → 2 → 3           → false

Copying the values into an array would be easy but uses O(n) space. Instead, we combine the two tools from this chapter:

  1. Find the middle with fast and slow pointers.

  2. Reverse the second half.

  3. Compare the first half and the reversed second half node by node.

  4. Reverse the second half again to restore the list (good manners: don't damage the caller's data).

1 → 2 → 3 → 2 → 1
        ↑ middle

After reversing from the middle:
first half:   1 → 2 → 3
second half:  1 → 2 → 3 → null   (reversed)

Compare: 1=1, 2=2, 3=3 → palindrome

We stop when the second-half pointer reaches null. For odd lengths, the middle node is compared with itself, which is harmless.

Complete Program: Fast and Slow Pointer Problems

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
    }
}

class Main {

    static Node build(int... values) {
        Node dummy = new Node(0);
        Node tail = dummy;
        for (int v : values) {
            tail.next = new Node(v);
            tail = tail.next;
        }
        return dummy.next;
    }

    static void print(Node head) {
        StringBuilder sb = new StringBuilder();
        for (Node cur = head; cur != null; cur = cur.next) {
            sb.append(cur.data).append(" -> ");
        }
        System.out.println(sb.append("null"));
    }

    static Node reverse(Node head) {
        Node prev = null;
        Node curr = head;
        while (curr != null) {
            Node next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }

    // Middle node (second middle when the length is even)
    static Node middle(Node head) {
        Node slow = head;
        Node fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    // Floyd's cycle detection
    static boolean hasCycle(Node head) {
        Node slow = head;
        Node fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                return true;
            }
        }
        return false;
    }

    // Returns the first node of the cycle, or null if there is no cycle
    static Node cycleStart(Node head) {
        Node slow = head;
        Node fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                Node p = head;          // phase 2
                while (p != slow) {
                    p = p.next;
                    slow = slow.next;
                }
                return p;
            }
        }
        return null;
    }

    // Number of nodes in the cycle (0 if there is no cycle)
    static int cycleLength(Node head) {
        Node slow = head;
        Node fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                int length = 1;
                Node cur = slow.next;
                while (cur != slow) {
                    length++;
                    cur = cur.next;
                }
                return length;
            }
        }
        return 0;
    }

    // Remove the n-th node from the end (1-based), one pass
    static Node removeNthFromEnd(Node head, int n) {
        Node dummy = new Node(0);
        dummy.next = head;
        Node fast = dummy;
        Node slow = dummy;

        for (int i = 0; i < n; i++) {   // create a gap of n nodes
            fast = fast.next;
        }
        while (fast.next != null) {     // move both until fast is at the last node
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;     // slow is just before the node to delete
        return dummy.next;
    }

    // Palindrome check in O(n) time and O(1) extra space
    static boolean isPalindrome(Node head) {
        Node secondHalf = reverse(middle(head));
        Node p1 = head;
        Node p2 = secondHalf;
        boolean result = true;
        while (p2 != null) {
            if (p1.data != p2.data) {
                result = false;
                break;
            }
            p1 = p1.next;
            p2 = p2.next;
        }
        reverse(secondHalf);            // restore the original list
        return result;
    }

    public static void main(String[] args) {

        System.out.println("Middle of 1..5: " + middle(build(1, 2, 3, 4, 5)).data);
        System.out.println("Middle of 1..6: " + middle(build(1, 2, 3, 4, 5, 6)).data);

        // Build 1 -> 2 -> 3 -> 4 -> 5 -> 6 and link 6 back to 3
        Node head = build(1, 2, 3, 4, 5, 6);
        Node third = head.next.next;
        Node last = third.next.next.next;
        last.next = third;

        System.out.println("Has cycle: " + hasCycle(head));
        System.out.println("Cycle starts at: " + cycleStart(head).data);
        System.out.println("Cycle length: " + cycleLength(head));
        System.out.println("Has cycle (1..5): " + hasCycle(build(1, 2, 3, 4, 5)));

        System.out.print("Remove 2nd from end: ");
        print(removeNthFromEnd(build(10, 20, 30, 40, 50), 2));
        System.out.print("Remove 5th from end: ");
        print(removeNthFromEnd(build(10, 20, 30, 40, 50), 5));

        Node pal = build(1, 2, 3, 2, 1);
        System.out.println("1 2 3 2 1 palindrome: " + isPalindrome(pal));
        System.out.println("1 2 2 1 palindrome: " + isPalindrome(build(1, 2, 2, 1)));
        System.out.println("1 2 3 palindrome: " + isPalindrome(build(1, 2, 3)));
        System.out.print("List after check: ");
        print(pal);
    }
}

Output:

Middle of 1..5: 3
Middle of 1..6: 4
Has cycle: true
Cycle starts at: 3
Cycle length: 4
Has cycle (1..5): false
Remove 2nd from end: 10 -> 20 -> 30 -> 50 -> null
Remove 5th from end: 20 -> 30 -> 40 -> 50 -> null
1 2 3 2 1 palindrome: true
1 2 2 1 palindrome: true
1 2 3 palindrome: false
List after check: 1 -> 2 -> 3 -> 2 -> 1 -> null

Notice that we never call print on the list with a cycle. Printing it would loop forever, which is exactly the problem cycle detection protects us from.

Time and Space Complexity

Problem

Technique

Time

Extra space

Reverse a list

Three pointers

O(n)

O(1)

Reverse a list (recursive)

Recursion

O(n)

O(n)

Reverse positions left..right

Dummy + three pointers

O(n)

O(1)

Merge two sorted lists

Dummy + tail

O(n + m)

O(1)

Middle node

Fast and slow

O(n)

O(1)

Detect cycle

Floyd (fast and slow)

O(n)

O(1)

Cycle start / length

Floyd + second phase

O(n)

O(1)

Remove n-th from end

Gap of n + dummy

O(n), one pass

O(1)

Palindrome list

Middle + reverse

O(n)

O(1)

Which Technique Should I Use?

If the problem says...

Think of...

"reverse", "in reverse order", "reverse in groups"

Three-pointer reversal

"middle", "split into two halves"

Fast and slow pointers

"cycle", "loop", "does it end?"

Floyd's algorithm

"k-th from the end", "one pass"

Two pointers with a gap of k

"palindrome", "compare first half with second half"

Middle + reverse second half

The head might be deleted or changed

Dummy node

Common Mistakes

1. Losing the rest of the list

Writing curr.next = prev before saving curr.next cuts the list, and the remaining nodes are lost. Always save next first.

2. Returning the wrong head after reversal

When the loop ends, curr is null. The new head is prev. Also remember to use the returned value: head = reverse(head);. Calling reverse(head) and continuing to use the old head leaves you with a one-node list.

3. Wrong loop condition for fast

Checking only fast != null crashes on fast.next.next for odd-length lists (including a single node): fast lands on the last node, fast.next is null, and null.next throws a NullPointerException. Use fast != null && fast.next != null.

4. Comparing values instead of nodes in cycle detection

Use slow == fast (same node object), not slow.data == fast.data. Two different nodes can hold the same value.

5. Checking for the meeting before moving

Both pointers start at head, so slow == fast is true at the start. Move first, then compare.

6. Forgetting the head-deletion case

Deleting the first node, or reversing from position 1, changes the head. Without a dummy node you need special if statements, and they are easy to get wrong.

7. Forgetting the recursion limit

Recursive reversal uses one stack frame per node. For lists with hundreds of thousands of nodes, the iterative version is the safe choice.

Interview Tips

  • Draw the boxes and arrows. Linked list bugs are almost always about the order of pointer updates. Drawing three or four nodes and updating arrows by hand catches them quickly.

  • Test four cases out loud: empty list, one node, two nodes, and a normal list (odd and even lengths for middle-based problems).

  • Write iterative reversal from memory. It is a building block for harder problems: reverse in groups of k, reorder list, add two numbers stored in reverse, and palindrome list.

  • Be ready to prove Floyd's algorithm. "The gap shrinks by one each step, so they must meet" and the equation a = (k - 1)c + (c - b) are what interviewers look for.

  • Mention the space trade-off. A set of visited nodes or an array copy works, but uses O(n) extra space. The pointer techniques use O(1).

  • Ask whether you may modify the list. If not, restore it (as in our palindrome solution) or use extra space.

Practice Problems

  1. Reverse Linked List

  2. Reverse Linked List II (reverse between positions)

  3. Middle of the Linked List

  4. Linked List Cycle

  5. Linked List Cycle II (find the start)

  6. Remove Nth Node From End of List

  7. Palindrome Linked List

  8. Merge Two Sorted Lists

  9. Reorder List (middle + reverse + merge)

  10. Reverse Nodes in k-Group (hard)

The Main Idea

Most linked list interview problems are built from a few small, reusable moves:

Reverse:      next = curr.next; curr.next = prev; prev = curr; curr = next;
Middle:       slow += 1, fast += 2, until fast reaches the end
Cycle:        slow += 1, fast += 2, a meeting means a cycle
Cycle start:  restart one pointer at head, move both by 1, meet at start
K-th from end: give fast a head start of k, then move both by 1
Dummy node:   put a fake node before head so the head is never special

Save the next node before you change a link, let a fast pointer explore ahead of a slow one, and put a dummy node in front of the head. With these three habits, most linked list problems become short, O(1)-space solutions.