Linked List Problems

Linked list problems test pointer manipulation under pressure. Almost all of them use three techniques: a dummy head node to simplify edge cases, fast and slow pointers, and in-place reversal. Master those and most list questions become variations.

1. Reverse a linked list iteratively and recursively.

Iterative: walk the list and point each node back to its predecessor — O(n) time, O(1) space. Recursive: reverse the rest, then attach the current node at the end — O(n) stack space.

ListNode reverse(ListNode head) {
    ListNode prev = null, cur = head;
    while (cur != null) {
        ListNode next = cur.next;
        cur.next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

ListNode reverseRec(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode newHead = reverseRec(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
}

2. Find the middle node in one pass.

Fast and slow pointers: slow moves one step, fast moves two. When fast reaches the end, slow is in the middle (the second middle for even lengths).

ListNode middle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }
    return slow;
}

3. Detect a cycle and find where it starts.

Floyd's algorithm: if fast and slow meet, there is a cycle. Then move one pointer back to the head and advance both one step at a time — they meet at the cycle's start. O(n) time, O(1) space.

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

4. Merge two sorted linked lists.

Use a dummy node and a tail pointer; always attach the smaller head, then append whatever remains. O(n + m).

ListNode merge(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; }
        else { tail.next = b; b = b.next; }
        tail = tail.next;
    }
    tail.next = (a != null) ? a : b;
    return dummy.next;
}

5. Remove the nth node from the end in one pass.

Move a lead pointer n steps ahead, then move both pointers until the lead reaches the end; the trailing pointer is just before the node to remove. A dummy head handles removing the first node.

ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0, head), lead = dummy, trail = dummy;
    for (int i = 0; i <= n; i++) lead = lead.next;
    while (lead != null) { lead = lead.next; trail = trail.next; }
    trail.next = trail.next.next;
    return dummy.next;
}

6. Check whether a linked list is a palindrome in O(1) space.

Find the middle, reverse the second half, compare the two halves node by node, then (politely) reverse the second half back to restore the list.

boolean isPalindrome(ListNode head) {
    ListNode mid = middle(head), second = reverse(mid), p = head, q = second;
    boolean ok = true;
    while (q != null) {
        if (p.val != q.val) { ok = false; break; }
        p = p.next; q = q.next;
    }
    reverse(second);       // restore
    return ok;
}

7. Find the intersection node of two lists.

Walk both lists with two pointers; when one reaches the end, restart it at the other list's head. Both travel the same total distance, so they meet at the intersection (or both become null).

ListNode intersection(ListNode a, ListNode b) {
    ListNode p = a, q = b;
    while (p != q) {
        p = (p == null) ? b : p.next;
        q = (q == null) ? a : q.next;
    }
    return p;
}

8. When would you choose a linked list over an array?

When you need frequent insertions and deletions at known positions (O(1) once you hold the node), or constant-time splicing — for example LRU caches (with a hash map) and undo lists. Arrays win for random access and cache-friendly iteration, which is why they are the default.