Linked List Interview Problems: Reversal, Fast-Slow Pointers and Every Classic Pattern

Linked list questions rarely need a clever algorithm. They test whether you can rewire references without dropping half the list, handle the head and tail without special-case spaghetti, and reason about two pointers moving at different speeds. That makes them common in online assessments and early rounds at companies like Amazon, Microsoft, Adobe and Indian product companies, and as components of design problems like the LRU cache.

Below are the four tools, the classic problems each one solves, and code in Java and Python. The node definitions used throughout:

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

Why Interviewers Still Ask Linked List Problems

Arrays give you random access; linked lists give you O(1) insertion and deletion once you hold a reference to the neighbouring node, at the cost of O(n) access by index and poor cache locality. In production code you rarely hand-roll one, but they are inside things you use daily: LinkedHashMap, LRU caches, free lists in memory allocators, and adjacency lists in graphs.

In interviews, they are a clean test of invariants and pointer discipline. A reviewer can see instantly whether you saved next before overwriting it, or whether your loop condition handles the last node. Clear narration matters: say what each pointer means before you move it.

Tool 1: The Dummy (Sentinel) Node

A dummy node before the head gives every real node a predecessor. Deleting the head, inserting before the head, or building a result list no longer needs an if (head == null) branch. You return dummy.next.

Remove Nth Node From End of List (LeetCode 19)

Move fast n + 1 steps ahead of slow (both starting at the dummy). Then advance both until fast is null; slow now sits just before the node to delete. One pass, and removing the head needs no special case.

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0, head);
    ListNode fast = dummy, slow = dummy;
    for (int i = 0; i <= n; i++) fast = fast.next;   // gap of n + 1
    while (fast != null) { fast = fast.next; slow = slow.next; }
    slow.next = slow.next.next;                      // unlink target
    return dummy.next;
}

def remove_nth_from_end(head, n):
    dummy = ListNode(0, head)
    fast = slow = dummy
    for _ in range(n + 1):
        fast = fast.next
    while fast:
        fast, slow = fast.next, slow.next
    slow.next = slow.next.next
    return dummy.next

Dry run on 1→2→3→4→5 with n = 2: after the gap, fast is at node 3 and slow at the dummy. Moving together, when fast becomes null slow is at 3, so node 4 is removed. With list [1] and n = 1, slow stays at the dummy and the head is removed cleanly, returning an empty list.

Other dummy-node problems: Remove Linked List Elements (203), Partition List (86, two dummies for "less than x" and "the rest"), Merge Two Sorted Lists, and Add Two Numbers.

Tool 2: In-Place Reversal and Its Variants

Reverse the whole list (LeetCode 206)

Three pointers: prev (already reversed part), cur (node being processed), and a saved next.

public ListNode reverseList(ListNode head) {
    ListNode prev = null, cur = head;
    while (cur != null) {
        ListNode next = cur.next;   // 1. save
        cur.next = prev;            // 2. flip
        prev = cur;                 // 3. advance prev
        cur = next;                 // 4. advance cur
    }
    return prev;
}

def reverse_list(head):
    prev, cur = None, head
    while cur:
        cur.next, prev, cur = prev, cur, cur.next   # RHS evaluated first, so this is safe
    return prev

def reverse_list_recursive(head):
    if head is None or head.next is None:
        return head
    new_head = reverse_list_recursive(head.next)
    head.next.next = head          # the node after head now points back to head
    head.next = None
    return new_head

Dry run for 1→2→3: (prev=null, cur=1) → 1 points to null, (prev=1, cur=2) → 2 points to 1, (prev=2, cur=3) → 3 points to 2, (prev=3, cur=null). Return 3: 3→2→1. The recursive version uses O(n) stack space; on a list with 10⁵ nodes it can overflow the default Java stack, so prefer iteration and mention why.

Reverse a sub-range: Reverse Linked List II (LeetCode 92)

Walk prev to the node before position left, then repeatedly take the node after cur and move it to the front of the sub-range ("head insertion"). After right - left moves, the range is reversed.

def reverse_between(head, left, right):
    dummy = ListNode(0, head)
    prev = dummy
    for _ in range(left - 1):
        prev = prev.next
    cur = prev.next                     # will end up as the last node of the range
    for _ in range(right - left):
        nxt = cur.next
        cur.next = nxt.next             # detach nxt
        nxt.next = prev.next            # insert nxt at the front of the range
        prev.next = nxt
    return dummy.next

For 1→2→3→4→5 with left 2, right 4: move 3 to the front (1→3→2→4→5), then move 4 to the front (1→4→3→2→5). Done, without ever disconnecting the list.

Reverse Nodes in k-Group (LeetCode 25, Hard)

Repeat: find the k-th node from the group's predecessor; if it does not exist, stop (leftover nodes stay as they are). Reverse the group with prev initialised to the node after the group, so the reversed group's tail automatically connects onward. Then link the predecessor to the new group head.

public ListNode reverseKGroup(ListNode head, int k) {
    ListNode dummy = new ListNode(0, head);
    ListNode groupPrev = dummy;
    while (true) {
        ListNode kth = groupPrev;
        for (int i = 0; i < k && kth != null; i++) kth = kth.next;
        if (kth == null) break;                       // fewer than k nodes remain
        ListNode groupNext = kth.next;

        ListNode prev = groupNext, cur = groupPrev.next;
        while (cur != groupNext) {                    // standard reversal within the group
            ListNode next = cur.next;
            cur.next = prev;
            prev = cur;
            cur = next;
        }
        ListNode oldFirst = groupPrev.next;           // becomes the group's tail
        groupPrev.next = kth;                         // kth is the new group head
        groupPrev = oldFirst;
    }
    return dummy.next;
}

Time O(n), space O(1). Narrating the two invariants ("groupPrev is the node before the current group" and "prev starts at groupNext") is what makes this Hard problem look easy.

Tool 3: Fast and Slow Pointers

Two pointers moving at different speeds reveal structure without extra memory: the middle, cycles, and the k-th node from the end.

Middle of the list (LeetCode 876)

public ListNode middleNode(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;     // for even length, the SECOND middle
}

For even lengths this returns the second middle (node 4 of 1..6). For merge sort and palindrome checks you often want the first middle, so start fast at head.next or loop while fast.next != null && fast.next.next != null. Knowing which one you need is a common source of off-by-one bugs.

Detect a cycle and find its start (LeetCode 141 and 142)

def detect_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:                 # they met inside the cycle
            p = head
            while p is not slow:         # move both one step at a time
                p = p.next
                slow = slow.next
            return p                     # cycle start
    return None

public ListNode detectCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            ListNode p = head;
            while (p != slow) { p = p.next; slow = slow.next; }
            return p;
        }
    }
    return null;
}

A HashSet of visited nodes also works in O(n) space; interviewers almost always ask for the O(1)-space version next.

Why Floyd's Cycle Detection Works: The Proof Interviewers Ask For

Part 1: they must meet. Once the slow pointer enters the cycle, the fast pointer is somewhere in the cycle too. Each step, fast moves 2 and slow moves 1, so the distance from fast to slow (measured along the cycle) shrinks by exactly 1. A gap that decreases by 1 each step must hit 0; fast cannot "jump over" slow. They meet within one lap of slow.

Part 2: finding the start. Let:

• a = number of steps from head to the cycle start,
• b = steps from the cycle start to the meeting point,
• c = cycle length.

At the meeting, slow has walked a + b and fast has walked 2(a + b). Fast has done some whole number k of extra laps, so 2(a + b) = a + b + kc, giving a + b = kc, i.e. a = kc - b = (k - 1)c + (c - b).

Now c - b is exactly the distance from the meeting point forward to the cycle start. So a pointer starting at the head and a pointer starting at the meeting point, both moving one step at a time, arrive at the cycle start together after a steps (the second one goes around k - 1 extra full laps). That is why the second loop returns the start.

Cycle length is a free follow-up: after meeting, keep slow fixed and walk one pointer around until it returns, counting steps. Find the Duplicate Number (287) applies the same algorithm to an array where i → nums[i] defines the "next" pointer: the duplicate value is the cycle start.

Tool 4: Merging and Splitting Lists

Merge Two Sorted Lists (LeetCode 21)

public ListNode mergeTwoLists(ListNode a, ListNode b) {
    ListNode dummy = new ListNode(0), tail = dummy;
    while (a != null && b != null) {
        if (a.val <= b.val) { tail.next = a; a = a.next; }   // <= keeps the merge stable
        else { tail.next = b; b = b.next; }
        tail = tail.next;
    }
    tail.next = (a != null) ? a : b;                         // attach the remainder
    return dummy.next;
}

O(n + m) time, O(1) extra space: nodes are relinked, not copied.

Merge k Sorted Lists (LeetCode 23)

Push each list's head into a min-heap; repeatedly pop the smallest, append it, and push its successor. With N total nodes and k lists, that is O(N log k). The alternative, pairwise divide-and-conquer merging, has the same bound and O(1) extra space apart from recursion.

import heapq

def merge_k_lists(lists):
    heap = [(node.val, i, node) for i, node in enumerate(lists) if node]
    heapq.heapify(heap)
    dummy = tail = ListNode()
    while heap:
        val, i, node = heapq.heappop(heap)
        tail.next = node
        tail = node
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))
    return dummy.next

The index i in the tuple is a tie-breaker: without it, two equal values make Python compare ListNode objects and raise TypeError. In Java, use new PriorityQueue<ListNode>((x, y) -> Integer.compare(x.val, y.val)). More heap patterns: heap and priority queue problems.

Sort List in O(n log n) (LeetCode 148)

Merge sort is the natural fit for linked lists: splitting at the middle uses fast/slow pointers and merging needs no extra array.

def sort_list(head):
    if not head or not head.next:
        return head
    slow, fast = head, head.next          # first middle, so a 2-node list splits 1 + 1
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
    mid, slow.next = slow.next, None      # cut the list in two
    left, right = sort_list(head), sort_list(mid)
    dummy = tail = ListNode()
    while left and right:
        if left.val <= right.val:
            tail.next, left = left, left.next
        else:
            tail.next, right = right, right.next
        tail = tail.next
    tail.next = left or right
    return dummy.next

Starting fast at head.next matters: with fast = head, a two-node list would never split and recursion would not terminate.

Copy List With Random Pointer (LeetCode 138)

Each node has next and a random pointer to any node or null. Deep-copy the list.

Approach 1: hashmap, O(n) space. First pass creates a copy of every node in a map original → copy. Second pass sets copy.next = map[orig.next] and copy.random = map[orig.random]. Simple and the right first answer.

Approach 2: interleaving, O(1) extra space. Weave each copy directly after its original (A→A'→B→B'), so the copy of any node X is simply X.next. Then A'.random = A.random.next. Finally unweave the two lists.

class Node:
    def __init__(self, val, next=None, random=None):
        self.val, self.next, self.random = val, next, random

def copy_random_list(head):
    if not head:
        return None
    cur = head
    while cur:                                   # 1. interleave copies
        cur.next = Node(cur.val, cur.next)
        cur = cur.next.next
    cur = head
    while cur:                                   # 2. wire random pointers
        if cur.random:
            cur.next.random = cur.random.next
        cur = cur.next.next
    cur, copy_head = head, head.next
    while cur:                                   # 3. separate the lists, restoring the original
        copy = cur.next
        cur.next = copy.next
        copy.next = copy.next.next if copy.next else None
        cur = cur.next
    return copy_head

public Node copyRandomList(Node head) {
    Map<Node, Node> copy = new HashMap<>();
    for (Node c = head; c != null; c = c.next) copy.put(c, new Node(c.val));
    for (Node c = head; c != null; c = c.next) {
        copy.get(c).next = copy.get(c.next);       // get(null) returns null: fine
        copy.get(c).random = copy.get(c.random);
    }
    return copy.get(head);
}

Interviewers expect you to mention that step 3 restores the original list. Leaving the input modified is considered a bug. The same "map from original to clone" idea solves Clone Graph; see the hashmap patterns guide.

More Classic Linked List Problems

Palindrome Linked List (234): combine three tools

Find the first middle (fast/slow), reverse the second half, compare both halves node by node, then reverse the second half back. O(n) time, O(1) space.

public boolean isPalindrome(ListNode head) {
    if (head == null || head.next == null) return true;
    ListNode slow = head, fast = head;
    while (fast.next != null && fast.next.next != null) { slow = slow.next; fast = fast.next.next; }
    ListNode second = reverseList(slow.next);      // reverseList from the reversal section
    boolean ok = true;
    for (ListNode p = head, q = second; q != null; p = p.next, q = q.next)
        if (p.val != q.val) { ok = false; break; }
    slow.next = reverseList(second);               // restore the input
    return ok;
}

Reorder List (143)

Turn L0→L1→...→Ln into L0→Ln→L1→Ln-1→... The same three steps: split at the middle, reverse the second half, then merge alternately. It is the best single problem for checking you have all the tools.

Intersection of Two Linked Lists (160)

Walk pointer p through A then B, and q through B then A. Both travel lenA + lenB steps, so they align at the intersection node, or both reach null together if there is none.

def get_intersection_node(a, b):
    p, q = a, b
    while p is not q:
        p = p.next if p else b
        q = q.next if q else a
    return p

Add Two Numbers (2)

Digits are stored in reverse order. Walk both lists with a carry and a dummy result head; continue while either list has nodes or carry is non-zero, which handles 5 + 5 = 10 producing an extra node. For digits in forward order (445), reverse both inputs first or use two stacks.

Odd Even Linked List (328) and Rotate List (61)

Odd Even: maintain two tails, one for odd positions and one for even, then attach the even list after the odd one. Rotate: compute length, connect the tail to the head to form a ring, then break it at position length - k % length.

LRU Cache (146)

A doubly linked list (for O(1) move-to-front and evict-from-tail) plus a hashmap from key to node. It is the most common place linked lists appear in design-flavoured rounds; see LRU cache explained.

Linked List Problems: Complexity Summary

Linked List Practice List

Linked List Interview Tips: How to Avoid Pointer Bugs

1. Draw it. Three or four boxes with arrows on the whiteboard or in comments. Update the drawing as you narrate each assignment.
2. Name what each pointer means before the loop: "prev is the head of the already-reversed part".
3. Save before you overwrite. Any time you assign x.next, ask whether you still need the old value.
4. Guard double steps. fast.next.next requires both fast and fast.next to be non-null.
5. Test tiny inputs: empty, one node, two nodes, and for k-group a length that is not a multiple of k.
6. Ask about mutation. "May I modify the input list?" If not, restore it (palindrome, random pointer) or copy.

Follow-ups interviewers commonly ask

• "Do it in O(1) extra space": reversal instead of a stack, interleaving instead of a map, Floyd instead of a set.
• "Do it recursively": reversal and merge both have elegant recursive forms; mention the stack-depth risk.
• "What if it's doubly linked?": deletion becomes O(1) given only the node, which is why LRU caches use doubly linked lists.
• "Delete a node given only that node" (237): copy the next node's value into it and unlink the next node. It cannot work for the tail, which is worth stating.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.