DSA Series: Linked List (Blind 75, Java)

Overview

• Pattern cheat-sheet
• Shared definition (used by every solution below)
• 1. Reverse Linked List (Easy · LeetCode #206)
• 2. Linked List Cycle (Easy · LeetCode #141)
• 3. Merge Two Sorted Lists (Easy · LeetCode #21)
• 4. Merge k Sorted Lists (Hard · LeetCode #23)
• 5. Remove Nth Node From End of List (Medium · LeetCode #19)
• 6. Reorder List (Medium · LeetCode #143)

Part of the DSA Blind 75 series. Track your progress on the Interview Prep page.

Java 11+. All code in this file was compiled and tested with asserts (examples, edge cases, and randomized checks for merge-k).

Pattern cheat-sheet

Rules of thumb: draw boxes and arrows; always save next before overwriting a pointer; always ask "what if the list is empty or has one node?"; use a dummy node whenever the head might be removed.

Shared definition (used by every solution below)

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

1. Reverse Linked List (Easy · LeetCode #206)

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

• [1,2,3,4,5] -> [5,4,3,2,1]; [1,2] -> [2,1]; [] -> [].
• Constraints: 0 <= n <= 5000, -5000 <= val <= 5000.

How the interviewer asks / follow-ups.

• Plain: "Reverse a singly linked list." Fintech disguise: "A ledger of entries is stored as a singly linked list oldest-first; give me newest-first without allocating new nodes."
• Follow-ups: do it iteratively AND recursively; what is the recursion depth risk (stack overflow at ~10^4-10^5 nodes in Java)? Reverse only a sub-range [m, n] (LC 92)? Reverse in groups of k (LC 25)? Can you do it with O(1) extra space?
• Evaluating: pointer manipulation without losing nodes, handling null/single node, ability to explain recursion's call stack.

Approach 1: Brute force. Copy values into an ArrayList (or push nodes on a stack), then rewrite values/links in reverse order. Time O(n), space O(n). Works but uses extra memory and (if you rewrite values) does not really relink nodes.

Approach 2: Iterative pointer reversal (optimal). Intuition: walk once, flipping each next to point backwards. Keep prev (reversed part), cur (node being processed), and save cur.next before overwriting it. Trace on 1->2->3: prev=null,cur=1 -> save next=2, 1.next=null, prev=1, cur=2 -> 2.next=1, prev=2, cur=3 -> 3.next=2, prev=3, cur=null. Return prev=3 giving 3->2->1.

Approach 3: Recursive. Intuition: trust that reverse(head.next) returns the reversed rest; head.next is now the tail of that reversed part, so set head.next.next = head and head.next = null. Trace on 1->2->3: recurse to 3 (base, returns 3). Back at 2: 2.next is 3, so 3.next=2, 2.next=null => 3->2. Back at 1: 2.next=1, 1.next=null => 3->2->1.

Java code.

// Iterative: O(n) time, O(1) space
static ListNode reverseIterative(ListNode head) {
    ListNode prev = null, cur = head;
    while (cur != null) {
        ListNode next = cur.next; // save before overwriting
        cur.next = prev;          // flip the link
        prev = cur;               // advance prev
        cur = next;               // advance cur
    }
    return prev;                  // new head (null for empty list)
}

// Recursive: O(n) time, O(n) call stack
static ListNode reverseRecursive(ListNode head) {
    if (head == null || head.next == null) return head; // empty or last node
    ListNode newHead = reverseRecursive(head.next);     // reverse the rest
    head.next.next = head;                              // old successor points back to head
    head.next = null;                                   // head becomes tail (avoids a cycle)
    return newHead;
}

Complexity.

• Brute (array/stack): Time O(n), Space O(n) - one pass to store, one to write.
• Iterative: Time O(n), Space O(1) - single pass, three pointers.
• Recursive: Time O(n), Space O(n) - one stack frame per node (risk of StackOverflowError for very long lists).

Edge cases / pitfalls.

• Empty list and single node (return as is).
• Forgetting head.next = null in recursion creates a cycle.
• Losing the rest of the list by overwriting cur.next before saving it.
• Mention Java's recursion depth limit and prefer iterative in production.

Pattern & related problems. In-place reversal. Related: Reverse Linked List II (92), Reverse Nodes in k-Group (25), Palindrome Linked List (234), Reorder List (143, below), Swap Nodes in Pairs (24).

2. Linked List Cycle (Easy · LeetCode #141)

Problem statement. Given head, return true if the list contains a cycle (some node's next points to an earlier node).

• 3->2->0->-4 with tail linking to node 2 -> true; 1->2 (no cycle) -> false; [] -> false.
• Constraints: 0 <= n <= 10^4. Follow-up: O(1) memory.

How the interviewer asks / follow-ups.

• Disguise: "A chain of retry/forwarding records (each points to the next hop) - detect whether a message can loop forever between routers/queues," or "detect circular dependency in a chain of settlement references."
• Follow-ups: find the node where the cycle begins (LC 142); find cycle length; why does Floyd's algorithm always meet? What if fast moves 3 steps? Can you do it without extra memory?
• Evaluating: knowledge of Floyd's tortoise and hare, null-guarding, ability to justify correctness.

Approach 1: Brute force / hash set. Store every visited node in a HashSet<ListNode> (identity-based); if you see one again there is a cycle. Time O(n), space O(n).

Approach 2: Floyd's fast/slow pointers (optimal). Intuition: if there is a cycle, fast gains one node per step on slow inside the loop, so the gap shrinks by 1 each iteration and must hit 0 (they meet). If no cycle, fast reaches null. Trace on 3->2->0->-4->(back to 2): (s,f) = (3,3) -> (2,0) -> (0,2) -> (-4,-4) meet => true.

Finding the cycle start (follow-up): after they meet, reset one pointer to head; move both one step at a time; they meet at the cycle entry. (If distance head->entry is a, entry->meeting point is b, cycle length is c, then 2(a+b) = a+b+kc, so a = kc - b: walking a steps from the meeting point lands on the entry.)

Java code.

static boolean hasCycle(ListNode head) {
    ListNode slow = head, fast = head;
    while (fast != null && fast.next != null) { // guard both for even/odd lengths
        slow = slow.next;                        // 1 step
        fast = fast.next.next;                   // 2 steps
        if (slow == fast) return true;           // compare references, not values
    }
    return false;                                // fast hit the end
}

// Follow-up: return the node where the cycle begins, or null
static 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) {
            ListNode p = head;
            while (p != slow) { p = p.next; slow = slow.next; }
            return p;
        }
    }
    return null;
}

Complexity.

• Hash set: Time O(n), Space O(n) - each node inserted once.
• Floyd: Time O(n), Space O(1) - fast catches slow within (tail length + cycle length) steps.

Edge cases / pitfalls.

• head == null, single node pointing to itself, two-node list.
• Compare node references (==), never val (duplicates are legal).
• Check fast != null && fast.next != null in that order to avoid NPE.
• Do not mutate the list (e.g. marking nodes) unless allowed.

Pattern & related problems. Fast/slow pointers. Related: Linked List Cycle II (142), Find the Duplicate Number (287), Happy Number (202), Middle of the Linked List (876).

3. Merge Two Sorted Lists (Easy · LeetCode #21)

Problem statement. Merge two sorted linked lists into one sorted list by splicing together the existing nodes; return its head.

• [1,2,4] + [1,3,4] -> [1,1,2,3,4,4]; [] + [0] -> [0]; [] + [] -> [].
• Constraints: each list length 0..50, values -100..100, both sorted non-decreasing.

How the interviewer asks / follow-ups.

• Disguise: "Two time-ordered transaction feeds (UPI and card) from two services - produce a single time-ordered feed."
• Follow-ups: stable merge (ties keep list A first)? Recursive version? Do it without allocating new nodes? What if lists are huge/streamed (merge lazily with iterators)? Extend to k lists (next problem).
• Evaluating: dummy-node technique, tie handling, appending the leftover tail in O(1).

Approach 1: Brute force. Dump all values into an array, sort, rebuild a list. Time O((m+n) log(m+n)), space O(m+n). Ignores that inputs are already sorted and allocates new nodes.

Approach 2: Two-pointer merge with dummy node (optimal). Intuition: like the merge step of merge sort. Compare heads, attach the smaller to tail, advance. When one list ends, attach the remainder of the other directly (it is already sorted). Trace [1,2,4] & [1,3,4]: take 1(a), 1(b), 2(a), 3(b), 4(a) then a is empty; append rest of b = 4. Result 1,1,2,3,4,4. Recursive alternative: if a.val <= b.val: a.next = merge(a.next, b); return a - O(m+n) stack.

Java code.

static ListNode mergeTwoLists(ListNode a, ListNode b) {
    ListNode dummy = new ListNode(0), tail = dummy; // dummy avoids special-casing the head
    while (a != null && b != null) {
        if (a.val <= b.val) { tail.next = a; a = a.next; } // <= keeps merge stable
        else                { tail.next = b; b = b.next; }
        tail = tail.next;
    }
    tail.next = (a != null) ? a : b; // splice remaining nodes in O(1)
    return dummy.next;
}

Complexity.

• Brute (sort): Time O((m+n) log(m+n)), Space O(m+n).
• Iterative merge: Time O(m+n), Space O(1) - each node is visited once, no new nodes.
• Recursive merge: Time O(m+n), Space O(m+n) - recursion depth.

Edge cases / pitfalls.

• One or both lists null (handled: loop skipped, tail.next = other or null).
• Duplicates across lists; use <= for stability.
• Forgetting to attach the leftover list.
• Returning dummy instead of dummy.next.

Pattern & related problems. Dummy node + two pointers. Related: Merge k Sorted Lists (23), Sort List (148), Merge Sorted Array (88), Add Two Numbers (2).

4. Merge k Sorted Lists (Hard · LeetCode #23)

Problem statement. Given an array of k sorted linked lists, merge them into one sorted list.

• [[1,4,5],[1,3,4],[2,6]] -> [1,1,2,3,4,4,5,6]; [] -> []; [[]] -> [].
• Constraints: 0 <= k <= 10^4, total nodes N <= 10^4, each list sorted ascending.

How the interviewer asks / follow-ups.

• Disguise: "Merge sorted transaction logs from k shards into one globally time-ordered audit stream." Or "k acquirer feeds, produce a reconciled ordered stream."
• Follow-ups: what if the logs are too big for memory (streaming k-way merge with a min-heap of file readers, emit incrementally)? What if one shard is much larger? What if k is huge or shards arrive dynamically? How would you distribute it (merge tree across machines)? What about ties (tie-break by shard id for determinism)? Compare heap vs divide and conquer.
• Evaluating: recognizing k-way merge, choosing a heap, complexity in terms of N and k, streaming mindset.

Approach 1: Brute force. Collect all N values, sort, rebuild. Time O(N log N), space O(N). Ignores sortedness. Another naive approach: merge lists one by one into an accumulator - worst case O(k·N) time because the accumulator is re-scanned each time.

Approach 2: Min-heap of list heads (k-way merge). Intuition: the next smallest overall must be among the current heads of the k lists. Keep those heads in a min-heap (size <= k); poll the min, append it, push its successor. Trace [1,4,5],[1,3,4],[2,6]: heap {1,1,2} -> poll 1 (push 4) -> poll 1 (push 3) -> poll 2 (push 6) -> poll 3 (push 4) -> poll 4 ... until empty. Output 1,1,2,3,4,4,5,6. This is the streaming-friendly approach: memory is O(k), not O(N).

Approach 3: Divide and conquer. Intuition: merge lists pairwise like a tournament; there are log k rounds and each round touches all N nodes. Reuses mergeTwoLists (from problem 3).

Java code.

// Heap approach
static ListNode mergeKLists(ListNode[] lists) {
    if (lists == null || lists.length == 0) return null;
    PriorityQueue<ListNode> pq = new PriorityQueue<>((x, y) -> Integer.compare(x.val, y.val));
    for (ListNode n : lists) if (n != null) pq.offer(n); // skip empty lists
    ListNode dummy = new ListNode(0), tail = dummy;
    while (!pq.isEmpty()) {
        ListNode n = pq.poll();            // smallest current head
        tail.next = n;
        tail = n;
        if (n.next != null) pq.offer(n.next); // push successor from the same list
    }
    return dummy.next;
}

// Divide and conquer approach (uses mergeTwoLists from problem 3)
static ListNode mergeKDC(ListNode[] lists) {
    if (lists == null || lists.length == 0) return null;
    return dc(lists, 0, lists.length - 1);
}
private static ListNode dc(ListNode[] l, int lo, int hi) {
    if (lo == hi) return l[lo];             // may be null, which is fine
    int mid = lo + (hi - lo) / 2;
    return mergeTwoLists(dc(l, lo, mid), dc(l, mid + 1, hi));
}

Complexity.

• Brute (collect and sort): Time O(N log N), Space O(N).
• Sequential one-by-one merge: Time O(k·N) worst case, Space O(1).
• Heap: Time O(N log k) - each of N nodes does one push and one poll on a heap of size <= k; Space O(k) for the heap.
• Divide and conquer: Time O(N log k) - log k levels each processing N nodes; Space O(log k) recursion (no extra nodes).

Edge cases / pitfalls.

• k = 0, array of nulls, some lists null (never offer null into the heap - NPE).
• Comparator: use Integer.compare not subtraction (overflow).
• Not stable across lists unless you tie-break by list index.
• Mention that the heap solution generalizes to files/iterators/Kafka partitions.

Pattern & related problems. K-way merge (heap) / divide and conquer. Related: Merge Two Sorted Lists (21), Find K Pairs with Smallest Sums (373), Kth Smallest in Sorted Matrix (378), Smallest Range Covering Elements from K Lists (632), Merge Sorted Array (88).

5. Remove Nth Node From End of List (Medium · LeetCode #19)

Problem statement. Remove the n-th node from the end of the list and return the head.

• [1,2,3,4,5], n=2 -> [1,2,3,5]; [1], n=1 -> []; [1,2], n=1 -> [1].
• Constraints: 1 <= size <= 30, 1 <= n <= size. Follow-up: one pass.

How the interviewer asks / follow-ups.

• Disguise: "Given a linked list of recent transactions, drop the k-th most recent entry without knowing the length," or "remove the N-th oldest entry from a bounded audit chain."
• Follow-ups: do it in a single pass; what if n > size (validate and return unchanged)? What if the list is doubly linked? Can you free/clean the removed node (set its next to null)?
• Evaluating: gap-pointer technique, dummy node to handle removing the head, off-by-one precision.

Approach 1: Brute force (two passes). Pass 1: count length L. Pass 2: walk to node at index L-n-1 and unlink the next one (special-case L == n, removing the head). Time O(L), space O(1) - fine, but two traversals.

Approach 2: Two pointers with a gap (one pass). Intuition: if fast is n nodes ahead of slow, when fast reaches the last node slow is just before the target. Start both at a dummy so the head can be removed uniformly. Trace [1,2,3,4,5], n=2: dummy->1->2->3->4->5. Move fast 2 steps -> at 2. Move both until fast.next == null: (fast,slow) = (3,1),(4,2),(5,3). slow.next is 4, which is the 2nd from the end; set slow.next = 5. Result 1,2,3,5.

Java code.

static ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0, head); // lets us delete the real head safely
    ListNode fast = dummy, slow = dummy;
    for (int i = 0; i < n; i++) {           // create an n-node gap
        fast = fast.next;                   // constraints guarantee n <= size; else validate for null
    }
    while (fast.next != null) {             // move until fast is on the last node
        fast = fast.next;
        slow = slow.next;
    }
    slow.next = slow.next.next;             // unlink target (slow is its predecessor)
    return dummy.next;
}

Complexity.

• Two-pass: Time O(L), Space O(1) - count then delete.
• One-pass gap pointers: Time O(L), Space O(1) - fast traverses the list once (same asymptotics, half the traversals in practice).

Edge cases / pitfalls.

• Removing the head (n == size) - needs the dummy.
• Single-node list.
• Off-by-one: stop when fast.next == null, not fast == null.
• If n can exceed size, null-check inside the gap loop and return head unchanged.

Pattern & related problems. Dummy node + gap (fast/slow) pointers. Related: Delete the Middle Node (2095), Remove Linked List Elements (203), Rotate List (61), Swap Nodes in Pairs (24).

6. Reorder List (Medium · LeetCode #143)

Problem statement. Reorder L0 -> L1 -> ... -> Ln-1 -> Ln into L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> ... in place (no value changes, no new nodes).

• [1,2,3,4] -> [1,4,2,3]; [1,2,3,4,5] -> [1,5,2,4,3].
• Constraints: 1 <= n <= 5*10^4, 1 <= val <= 1000.

How the interviewer asks / follow-ups.

• Disguise: "Interleave the oldest and newest entries of a transaction chain for a review UI (first, last, second, second-last...), in place."
• Follow-ups: O(1) extra space? Why not just use an array (it is O(n) space)? Do it recursively (and its stack cost)? What changes for a doubly linked list (it becomes trivial with two pointers)?
• Evaluating: composition of three sub-skills - find middle, reverse, merge/interleave; careful pointer handling.

Approach 1: Brute force. Put all nodes in an ArrayList<ListNode>; use indices i=0, j=n-1 to relink: nodes[i].next = nodes[j]; i++; nodes[j].next = nodes[i]; j-- and finally set the last next = null. Time O(n), space O(n).

Approach 2: Find middle + reverse second half + interleave (optimal). Intuition: the target order alternates front nodes with the back half read backwards. So (1) find the middle with fast/slow, (2) cut the list and reverse the second half, (3) weave the two halves. Trace 1->2->3->4->5: middle = 3 (slow stops there since fast.next.next is null at 5). Second half after 3 = 4->5, reversed 5->4; cut 3.next = null; first half 1->2->3. Weave: 1,5 | 2,4 | 3 => 1->5->2->4->3. For even length 1->2->3->4: slow stops at 2; second half 3->4 reversed 4->3; first half 1->2. Weave: 1,4 | 2,3 => 1->4->2->3.

Java code. (uses reverseIterative from problem 1)

static void reorderList(ListNode head) {
    if (head == null || head.next == null) return;

    // 1. Find the end of the first half (for even n, the left middle)
    ListNode slow = head, fast = head;
    while (fast.next != null && fast.next.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    // 2. Reverse the second half and cut the list in two
    ListNode second = reverseIterative(slow.next);
    slow.next = null;

    // 3. Interleave: first half is >= second half in length
    ListNode first = head;
    while (second != null) {
        ListNode t1 = first.next, t2 = second.next; // save next pointers
        first.next = second;
        second.next = t1;
        first = t1;
        second = t2;
    }
}

Complexity.

• Brute (array of nodes): Time O(n), Space O(n).
• Middle + reverse + merge: Time O(n) - three linear passes; Space O(1) - only pointers.

Edge cases / pitfalls.

• Lengths 0, 1, 2, 3 (the 3-node case 1,2,3 -> 1,3,2).
• Forgetting slow.next = null leaves a cycle/duplicate tail.
• Loop condition on the stopping middle: use fast.next != null && fast.next.next != null so the first half is the longer one for odd length.
• Interleave must loop on second, since first half is never shorter.

Pattern & related problems. Fast/slow + reversal + merge. Related: Palindrome Linked List (234), Reverse Linked List (206), Odd Even Linked List (328), Sort List (148).