Linked List

Pointer surgery without an array — dummy heads, fast/slow pointers, and the in-place reversal that solves half the questions.

intermediatePractice Full theoryPrereq:Two Pointers

Start practice Read the theory See all problems

What you'll learn

Manipulate next pointers without losing the remainder of the list
Use a dummy head to eliminate special-casing the first node
Reverse a linked list in place, iteratively and recursively
Apply fast/slow pointers for middle, cycle detection, and nth-from-end
Merge two sorted lists and detect/remove cycles
Reason about why linked-list ops are O(1) given the node, O(n) to find it

When to reach for this

Signals (use it)

Frequent insertions/deletions at known positions, no random access needed
"Reverse the list / reverse in groups of k"
"Find the middle", "nth node from the end", "detect a cycle"
"Merge two sorted lists"
The head node itself might be removed/changed → use a dummy

Anti-signals (don't)

You need index access or binary search → array
You need to sort by value repeatedly → array or heap
Cache-friendly contiguous storage matters → array

Theory & deep dive

A linked list stores elements in nodes, each holding a value and a pointer to the next node. Unlike an array, the nodes aren't contiguous in memory — you can only reach a node by following pointers from the head. That gives O(1) insertion/deletion once you hold the right node, but O(n) access by position (no indexing).

Linked-list interview questions are really pointer-manipulation puzzles. The difficulty is never the algorithm — it's not losing your place: reconnecting pointers in the right order, handling the head specially, and avoiding null dereferences. Three techniques defuse almost all of it: the dummy head sentinel (kills head edge-cases), fast/slow pointers (find middle, detect cycles, nth-from-end), and in-place reversal (the single most-tested operation).

This module gives you all three with safe templates and the order-of-operations that prevents the classic 'lost the rest of the list' bug.

The big idea in plain words

A linked list is a treasure hunt. Each clue (a node) holds a prize (a value) and tells you where the next clue is hidden. You can't leap straight to clue number five - you have to follow the trail from the very first clue. That is why there is no instant jump-to-index like an array gives you.

Example (reversing a list): to turn the trail around, flip each arrow to point backward, one at a time. The trick is to jot down where you were about to go before you flip the arrow, so you don't lose the rest of the trail. Three little pointers - previous, current, and the saved next - shuffle forward together until the whole list points the other way.

Node anatomy and core trade-offs

Concept	Meaning
Node	`{ val, next }` — a value plus a pointer to the next node
Head	First node; `null`/`None` head means empty list
Singly linked	Each node points only forward (`next`)
Doubly linked	Nodes also point back (`prev`) — O(1) delete given the node
Dummy / sentinel	A fake node before the head to simplify edge-cases

The defining trade-off versus an array:

Operation	Array	Linked list
Access by index	O(1)	O(n)
Insert/delete at known node	O(n) (shift)	O(1) (relink)
Search by value	O(n)	O(n)

Pick the technique by the task:

The dummy-head technique

Half of linked-list bugs come from the head being a special case (removing the first node, building a new list). A dummy head — a throwaway node placed before the real head — erases that special case: you always have a node before the one you're working on, so insertion and deletion are uniform. At the end, return dummy.next.

Reach for a dummy whenever the head might change: removing nodes, merging lists, partitioning.

Java· Remove all nodes with a target value (dummy head)

ListNode removeElements(ListNode head, int val) {
    ListNode dummy = new ListNode(0, head);
    ListNode prev = dummy;
    while (prev.next != null) {
        if (prev.next.val == val) prev.next = prev.next.next; // skip
        else prev = prev.next;
    }
    return dummy.next;   // real head, even if original head was removed
}

In-place reversal (the most-tested op)

Reversing a singly linked list is the operation behind reverse-list, reverse-in-k-groups, palindrome-check, and reorder-list. The iterative version walks the list once, flipping each next pointer to point backward, using three pointers: prev, curr, and a saved next.

The critical order of operations: save `next` before you overwrite `curr.next`, or you lose the rest of the list. Memorise the four-line dance.

Java· Reverse a linked list (iterative)

ListNode reverse(ListNode head) {
    ListNode prev = null, curr = head;
    while (curr != null) {
        ListNode nxt = curr.next; // save
        curr.next = prev;         // flip
        prev = curr;              // advance
        curr = nxt;
    }
    return prev;
}

Watch out

The #1 linked-list bug: overwriting curr.next before saving it. Always capture nxt = curr.next on the first line of the loop body.

Fast/slow pointers on lists

Two pointers from the head, fast moving twice as fast as slow, solve a cluster of problems in one pass with O(1) space:

Task	How
Find the middle	When `fast` hits the end, `slow` is at the middle
Detect a cycle	If `fast` ever equals `slow`, there's a loop (Floyd's)
Find cycle start	After meeting, reset one pointer to head; advance both 1× until they meet
Nth node from end	Advance `fast` n steps first, then move both until `fast` ends

This beats the naive 'store visited nodes in a hash set' approach on space — O(1) vs O(n).

Merging two sorted lists

Merging is the linked-list half of merge sort and a frequent standalone question. Use a dummy head and a tail pointer; repeatedly attach the smaller of the two front nodes and advance that list. When one list empties, attach the remainder of the other in O(1).

Python· Merge two sorted lists

def merge_two(l1, l2):
    dummy = tail = ListNode(0)
    while l1 and l2:
        if l1.val <= l2.val:
            tail.next, l1 = l1, l1.next
        else:
            tail.next, l2 = l2, l2.next
        tail = tail.next
    tail.next = l1 or l2     # attach the leftover
    return dummy.next

How to talk about this in the interview

“Draw the list and the pointers on the whiteboard first — interviewers expect it and it prevents lost-pointer bugs. Say: "I'll use a dummy head so I don't special-case the original head, and I'll save the next pointer before relinking so I never lose the tail." For middle/cycle problems, name fast/slow: "Two pointers, fast moving twice as fast — O(1) space instead of a hash set of visited nodes." State O(n) time, O(1) space.”

Common mistakes

–Overwriting `curr.next` before saving it — loses the rest of the list
–Not using a dummy head, then writing fragile special-cases for the first node
–Dereferencing `fast.next.next` without null-checking `fast` and `fast.next`
–Returning `head` instead of `dummy.next` after the head may have changed
–Creating a cycle by mis-ordering pointer assignments
–Using O(n) extra space (hash set) for cycle detection when fast/slow is O(1)

Complexity summary

Most linked-list algorithms are a single pass: O(n) time, O(1) space. Recursive reversal is O(n) time but O(n) stack space. Access by position is O(n); insertion/deletion is O(1) once you hold the predecessor node.