Linked List, Queue & Stack

Linked lists have no array indexing, no length field you can trust, and no safety net — one careless pointer move and you either drop half the list on the floor or tie it into an infinite loop. That fragility is exactly why they are an interview staple: a linked-list question is a pointer-discipline exam wearing a data-structure costume. This session builds the whole toolkit from one primitive — pointer reversal — and then shows how reversal, fast/slow pointers, dummy heads, and split-and-recombine cover almost every list problem you will be handed, from the gentle LC 206 up to reversing in k-groups.

A Linked List Is Not an Array

Start with where the bytes live. An array is a contiguous block on the heap, so element i is a single multiply-and-add away — O(1) random access. A linked list is a scatter of nodes anywhere on the heap, chained only by next references, so reaching the i-th node means walking i hops — O(n) access. You trade fast lookup for cheap splicing: inserting or deleting in the middle of a list is a couple of pointer swaps, no shifting.

The session spends real time on a distinction that trips people up in Java: a null reference is not an empty container. These are four different states:

• int[] arr = null — no array object on the heap at all; the reference points at nothing.
• int[] arr = new int[0] — a real array object exists on the heap, it just has zero capacity.
• ArrayList<Integer> ls = null — no list object; dereferencing throws immediately.
• ArrayList<Integer> ls = new ArrayList<>() — a real object with size == 0 but a non-zero backing capacity (the default is 10 on first insertion).

Say it as a rule: null means "no object in the heap for this reference"; size == 0 means "there is an object, it just has no valid value yet." Every list problem begins by deciding which of those two your input might be — that is what the head == null guard is really testing.

The Node, the Dummy, and the Corner Cases

The node itself is trivial, and that is the point — a tree node is the same object with two child pointers instead of one next, which is why the same reversal muscles carry over to trees later. Java's standard library backs both singly and doubly linked lists with one node type; the pre pointer just sits unused in the singly case.

class ListNode {
    int val;
    ListNode next;
    ListNode pre;              // one node type serves both singly & doubly linked
    ListNode(int val) {
        this.val = val;
        this.next = null;
        this.pre  = null;
    }
}

// a tree is the same idea — swap next for left/right
class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int val) { this.val = val; }
}

Two habits keep list code from imploding. First, the corner cases are always the same two: head == null (empty list) and head.next == null (a single node). Ninety percent of list functions open with if (head == null || head.next == null) return head;. Second, the main body is nearly always a while loop, and the only interesting design decision is where cur stands when the loop exits — decide that first and the post-processing writes itself.

And a word on the dummy node. ListNode dummy = new ListNode(0) is a fake node glued in front so that "insert before the head" stops being a special case. It is genuinely useful — merge, partition and insertion-sort all lean on it — but the instructor's note is worth repeating: use it only when you must. Some interviewers read a reflexive dummy as "can't handle a moving head," so prefer to manipulate the real head directly when the problem allows, and pull out the dummy only when the front of the list is genuinely unstable.

Reversal: The Mother Pattern (LC 206)

If you internalize one thing this session, make it this. LC 206 Reverse Linked List is the atom that half the other problems are built from. The iterative version walks three pointers down the list, flipping each next as it goes:

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode pre = null;   // the reversed part behind cur
    ListNode cur = head;   // the node we are flipping now
    ListNode next = null;  // stash so we don't lose the tail
    while (cur != null) {
        next = cur.next;   // 1. save the road ahead
        cur.next = pre;    // 2. flip the arrow backward
        pre = cur;         // 3. advance the reversed frontier
        cur = next;        // 4. step forward
    }
    return pre;            // cur is null; pre is the new head
}

The loop exits when cur reaches null, at which point pre sits on the last node visited — the new head. Note that next exists purely to obey law (1): the instant you write cur.next = pre you have destroyed the forward link, so you must have stashed it a line earlier or the rest of the list is gone.

The recursive version says the same thing top-down. "What is the reverse of the list headed at 1? I don't know — reverse the list headed at 2 first, then hook 1 onto its tail." The recursion bottoms out at the last node (that is the reversed result), then on the way back up each frame performs two assignments:

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;  // base case = reversed result
    ListNode newHead = reverseList(head.next);  // reverse everything after head
    // --- the wall: below here the tail is already reversed ---
    head.next.next = head;   // the node after head now points back at head
    head.next = null;      // head becomes the new tail, terminate it
    return newHead;          // same new head bubbles all the way up
}

There is a tempting wrong version worth flagging, because candidates write it constantly: do the pointer flip first and then recurse (head.next.next = head; head.next = null; return reverseList(next)). It fails for a subtle reason — once you null out head.next you have severed your only route back to the newly reversed head, so the frames can never reconnect and you return the wrong node. The rule: for reversal, recurse first, mutate on the way back. Iteration is O(1) space and the safe default; recursion is prettier but pays O(n) call stack and can blow the stack on a very long list.

Reversal Variants: Pairs, K-Groups, and Ranges

Once LC 206 is muscle memory, three "harder" problems are just reversal with a governor on how much you reverse at a time.

LC 24 Swap Nodes in Pairs reverses in chunks of two: 1→2→3→4 becomes 2→1→4→3. The recursive shape is LC 206 with the recursion jumping two nodes ahead (reverse(head.next.next)), flipping the current pair, and returning the pair's new front. LC 92 Reverse Linked List II reverses only the sub-list between positions m and n. This is the honest use case for a dummy node: park pre just before position m, then repeatedly pluck the node after start and splice it to the front of the reversed window — n − m splices and you are done, no special-casing when the reversal touches the real head.

LC 25 Reverse Nodes in k-Group is the crown jewel and a genuine "impressive if you nail it live" problem. First walk k nodes to confirm a full group exists (if it doesn't, the tail stays untouched — that is the spec). Recurse on the remainder to get the new head of everything downstream, then reverse this group of k and splice it on top:

public ListNode reverseKGroup(ListNode head, int k) {
    if (head == null || head.next == null || k < 2) return head;

    int i = k;
    ListNode tmp = head;
    while (i > 0 && tmp != null) {   // probe: is there a full group of k?
        tmp = tmp.next;
        i--;
    }
    if (i == 0) {                     // yes — tmp is the head of the rest
        ListNode newHead = reverseKGroup(tmp, k);  // solve the rest first
        i = k;
        ListNode next = null;
        while (i > 0) {              // reverse this group onto newHead
            next = head.next;
            head.next = newHead;
            newHead = head;
            head = next;
            i--;
        }
        head = newHead;
    }
    return head;                     // incomplete trailing group left as-is
}

The elegance: the whole family — single node, pair, k-group — is the identical reversal loop with a different stride, and the base/corner cases (head == null, head.next == null) never change.

Fast & Slow Pointers: Middle and K-th From End

The second big idea is running two pointers at different speeds down one pass. Finding the middle (LC 876) is the canonical use: advance slow one hop and fast two, and when fast falls off the end, slow is at the midpoint. The whole game is the loop condition, because it decides which node "the middle" means on an even-length list. Use fast.next != null && fast.next.next != null and slow lands on the lower-middle — precisely what you want before a split, since the front half keeps the extra node.

ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
    slow = slow.next;         // +1 per round
    fast = fast.next.next;    // +2 per round
}
// slow is the (lower) middle; slow.next starts the second half

The k-th node from the end (a LintCode classic, and the engine behind LC 19 Remove Nth Node From End) uses a fixed gap instead of a speed difference: march fast forward k steps first — checking fast != null each step so a too-large k returns null instead of throwing — then walk slow and fast together. When fast hits the end, slow is exactly k from the tail. One pass, no length precomputation.

Cycles: Detection, Length, and the a = c Trick

A "cycle" doesn't have to be a full loop — it's any node whose next re-enters part of the list, shaped like a lasso. Three ways to detect a repeated node: a hash set of visited nodes (O(n) space), a visited boolean field if you're allowed to mutate, or — the one interviewers want — fast/slow pointers in O(1) space. If fast ever laps slow, there is a cycle (LC 141); if fast runs off a null, there isn't.

Two follow-ups fall out of the meeting point. Cycle length: once they meet, freeze one pointer and walk the other around with a counter until it returns. Cycle entrance (LC 142): here is the beautiful part. Let a be the distance from the head to the loop entrance, b from the entrance to the meeting point, and c the rest of the loop. Slow has walked a + b; fast has walked twice that and gone one extra lap, so 2(a + b) = a + 2b + c, which collapses to a = c. Translation: the distance from the head to the entrance equals the distance from the meeting point back to the entrance. So reset one pointer to the head, step both one at a time, and they collide exactly at the entrance.

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) {          // they meet inside the loop
            fast = head;             // a = c, so reset one to head
            while (slow != fast) {    // walk in lockstep
                slow = slow.next;
                fast = fast.next;
            }
            return slow;             // collision == entrance
        }
    }
    return null;                    // fast fell off → no cycle
}

The same two-pointer-identity flavor powers LC 160 Intersection of Two Linked Lists: walk pointer a down list A then continue onto list B, and b down B then onto A. Both travel lenA + lenB total, so they arrive at the shared node together — or both reach null together if the lists never meet. The one detail interviewers probe: the loop must switch on a == null, not a.next == null. The no-intersection case ends with a == b == null; if you skipped the null state you would miss that termination and either spin forever or dereference null.

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if (headA == null || headB == null) return null;
    ListNode a = headA, b = headB;
    while (a != b) {
        a = (a == null) ? headB : a.next;   // null, NOT a.next: keep the null case
        b = (b == null) ? headA : b.next;
    }
    return a;   // the shared node, or null if disjoint
}

Deletion and the CRUD Mindset

The instructor frames every data structure as CRUD — create, read, update, delete — and even draws the analogy to a REST API (resources addressed by URL, operations named by HTTP verb) to make the point that "what operations does this thing support?" is a checklist worth running on any structure. For lists, deletion splits into two shapes.

Deleting with access to the predecessor is the easy case: pre.next = pre.next.next and the target is unlinked. Deleting when you only hold the node itself (LC 237) is the trick question — you can't reach backward, so you copy the successor's value into the current node and unlink the successor instead: node.val = node.next.val; node.next = node.next.next. You didn't delete "this" node, you impersonated the next one and deleted that.

• LC 203 Remove Linked List Elements — remove every node equal to val. First skip any matching prefix (while (head != null && head.val == val) head = head.next), then run a cur.next.val == val ? unlink : advance loop. There is a two-line recursive version too, but the notes flag it honestly: deep recursion here risks a stack overflow on long lists — prefer iteration.
• LC 83 Remove Duplicates from Sorted List — since equal values are adjacent, keep advancing while cur.val == cur.next.val, unlinking the copy, else step forward. Same skeleton as LC 203 with a different match predicate.
• LC 237 Delete Node in a Linked List — the copy-forward trick above, O(1), only valid when the node isn't the tail.

Merging and Sorting

LC 21 Merge Two Sorted Lists is the workhorse behind everything else in this section. Walk both lists, always splicing the smaller head onto a dummy-anchored tail, then attach whatever remains:

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null) return l2;
    if (l2 == null) return l1;
    ListNode dummy = new ListNode(0), tail = dummy;
    while (l1 != null && l2 != null) {
        if (l1.val < l2.val) { tail.next = l1; l1 = l1.next; }
        else                 { tail.next = l2; l2 = l2.next; }
        tail = tail.next;
    }
    tail.next = (l1 != null) ? l1 : l2;   // attach the leftover tail wholesale
    return dummy.next;
}

There is a clean recursive twin — if (l1.val < l2.val) { l1.next = merge(l1.next, l2); return l1; } and symmetrically — and it comes with a memorable lesson: the recursion's base cases are exactly the iteration's corner cases (l1 == null, l2 == null). If you can enumerate one, you can write the other.

LC 147 Insertion Sort List is then just "call insert repeatedly": maintain a sorted list behind a dummy, and for each incoming node, walk the sorted part to find its slot and splice it in — O(n²), stable, and the one subtlety is to stash cur.next before you splice, since the insert mutates cur.next and you'd otherwise lose your place in the input.

LC 148 Sort List wants O(n log n) in constant extra space, and "n log n on a linked list" should immediately say merge sort (quicksort's random access is a poor fit). Cut the list in half with fast/slow — and here is the bug that bites everyone: you must sever the first half with prev.next = null before recursing, or the two halves still point at each other. Sort each half recursively, then reuse the LC 21 merge. It's three primitives you already own, bolted together.

Split and Recombine

A whole family of problems reduces to "split the list into two by some rule, then weave them back." The template is identical; only the splitting predicate changes.

LC 143 Reorder List (1 2 3 … n → 1 n 2 (n-1) …) is the poster child for modular thinking. The naive route reverses the whole list and interleaves, but the in-place O(1)-space solution is three subroutines you've already written: find the middle, reverse the second half, merge the two halves alternately. Cut the halves with mid.next = null, and the rest is composition.

LC 328 Odd Even Linked List weaves by position: thread an odd chain and an even chain in one pass, then hook the even head onto the odd tail. LC 86 Partition List weaves by value: send nodes < x to a "smaller" list and the rest to a "larger" list, then concatenate. This one hides the single most common linked-list bug — you must set larger.next = null before joining, or the larger tail still references a node that migrated into the smaller list and you've built a cycle. Same disease as forgetting prev.next = null in Sort List and mid.next = null in Reorder: every time you split, terminate.

Arithmetic on Lists

Linked lists double as arbitrary-precision integers — one digit per node — which is why interviewers use them when a number would overflow int or long. LC 2 Add Two Numbers stores digits least-significant-first, so you add left to right with a running carry, minting one output node per step; the loop condition l1 != null || l2 != null || carry != 0 elegantly folds in the final carry-out (the 999 + 1 case) without a special branch.

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode dummy = new ListNode(0), head = dummy;
    int carry = 0;
    while (l1 != null || l2 != null || carry != 0) {   // carry keeps the loop alive
        int v1 = (l1 == null) ? 0 : l1.val;
        int v2 = (l2 == null) ? 0 : l2.val;
        int sum = carry + v1 + v2;
        head.next = new ListNode(sum % 10);
        carry = sum / 10;
        head = head.next;
        l1 = (l1 == null) ? null : l1.next;
        l2 = (l2 == null) ? null : l2.next;
    }
    return dummy.next;
}

LC 369 Plus One Linked List is the most-significant-first variant. Since you can only walk forward, the clean move is reverse, add one with carry, reverse back — or, without reversing, find the rightmost non-9 digit, bump it, and zero everything after it (and if the whole list is nines, prepend a fresh 1 node). Both are the carry mechanic in a different coordinate system, and both beat trying to do string arithmetic, which drowns in edge cases like empty strings and leading zeros.

Problem Checklist