Linked Lists

Nodes that hold a value and a reference to the next node — cheap to rewire, slow to index.

beginner~90 min7 simulations18 problems

▶ guided lesson ⚡ 1-minute summary ↻ 14 recall cards

before this: Arrays & Strings · Two Pointers · Big-O

Section

01 · why it exists

Why this exists, and the weight it carries

since1956

Singly linked list

Allen Newell, J. C. (Cliff) Shaw and Herbert A. Simon

In 1956 Newell, Shaw and Simon were building the Logic Theory Machine, a program that searched for proofs in logic. Its data grew in shapes and sizes nobody could predict, so a fixed block of memory per list would either overflow or sit half empty. Their fix: each memory cell points to the next one, and new cells come from a shared pool of free cells — the first list-processing languages (IPL). A 1960 paper already named the price: the links ate about half the fast memory, and reaching the k-th item got slow.

the problem it solvedStoring data whose size and shape you can't know in advance, without reserving big fixed blocks that overflow or sit empty.

its jobs today

Hash tables: Java's HashMap keeps colliding entries in a short linked chain per bucket (and turns very long chains into small trees since Java 8).
Free lists: memory allocators thread a linked list through the free blocks themselves, so grabbing or returning a block is O(1).
A building block for bigger structures: adjacency lists in graphs, the chain inside an LRU cache, and the linked queue of the next chapter.

the weight it carries

Illustrative: a sequence of 10 lakh (1,000,000) items. Insert at the front: linked list = 1 new node + 2 reference writes; ArrayList.add(0, x) = shift all 1,000,000 items. Read item #500,000: linked list = 500,000 hops; array = 1 address calculation (base + 500,000 × size).

without it

Every growing, splicing structure would need big up-front arrays and O(n) shifts — no cheap hash-table chains, free lists or O(1) cache eviction.

when · why · how

when: Lots of inserts and deletes at the front or next to nodes you already hold — and every interview problem that hands you a ListNode.
why: Splicing is O(1) because nothing shifts; the price is O(n) to reach the k-th node, plus an object and a reference per item — far less cache-friendly than an array.
how: A tiny class ListNode { int val; ListNode next; } and a head reference. For everyday sequences prefer ArrayList / ArrayDeque; java.util.LinkedList is the library's doubly linked version.

since?

Dummy head (sentinel node)

No single inventor: a dummy (sentinel) node is an old programming trick, passed down through textbooks rather than published as an algorithm.

its jobs today

Every "the head might change" problem — delete, partition, merge, reverse a section — runs one code path instead of a special case for the first node.
Doubly linked lists with a head and a tail sentinel (like the LRU cache here) link and unlink nodes without a single null check.

the weight it carries

Illustrative: delete every 7 from [7, 7, 7, 1]. Without a dummy: one loop strips the 3 leading 7s (moving head each time), then a second loop handles the rest — two code paths to get right. With a dummy: one loop over 4 nodes, 3 unlinks, then return dummy.next.

without it

List code fills up with if (head == null) and if (target == head) branches — the most common source of linked-list bugs.

when · why · how

when: The first node may be removed, replaced or preceded: deletes, merges, partitions, reversing a section, k-group.
why: It costs one extra node (O(1) space) and the same time, and removes a whole class of edge cases.
how: ListNode dummy = new ListNode(0, head); walk with prev = dummy, and always return dummy.next;.

since?

In-place reversal (prev / curr / next)

No single inventor: flipping links to reverse a list is list-processing folklore, taught in textbooks rather than credited to one paper.

its jobs today

A building block inside bigger list algorithms: palindrome check, reorder list, k-group reversal, and adding numbers stored most-significant digit first all reverse part of a list.
Functional-style queues keep two lists and reverse the back one when the front runs out — the same idea as the two-stack queue in the next chapter.

the weight it carries

Illustrative: reverse a list of 10 lakh nodes. The loop: 1,000,000 × 4 reference assignments and just 3 extra references. A stack copy: 1,000,000 extra references. Recursion: 1,000,000 stack frames — at roughly 100 bytes each that's about 100 MB of stack, against a default thread stack of about 1 MB.

without it

To read a list backwards you would copy it into an array or a stack every time — O(n) extra memory.

when · why · how

when: Anything that needs a list, or part of one, read backwards: reverse all, reverse a section, compare against the back half, reorder.
why: One pass, O(n) time and O(1) space. The recursive version is shorter but costs O(n) stack.
how: ListNode prev = null, curr = head; while (curr != null) { ListNode next = curr.next; curr.next = prev; prev = curr; curr = next; } return prev;

sinceIn print 1969

Fast & slow pointers (Floyd's cycle detection)

Robert W. Floyd (as credited by Donald E. Knuth); later Richard P. Brent

Knuth's The Art of Computer Programming, Vol. 2 (1969), gives the tortoise-and-hare idea as an exercise and credits it to Robert W. Floyd — its first known appearance in print. No paper by Floyd describing it is known, so it may be older folklore. In 1975 John Pollard built a method for factoring large numbers on this cycle finder (the "rho" method). In 1980 Richard Brent published a variant that is about 36% faster on average.

the problem it solvedNoticing that a sequence repeats — and where the repeat begins — with two pointers, without storing everything you have seen.

its jobs today

Finding repeats where storing every state is too costly: Pollard's rho factoring is built on it, and Knuth uses it to study when a pseudo-random number generator starts repeating.
Linked lists in one pass and O(1) space: the middle (to split for merge sort or a palindrome check), a cycle and its entry, the n-th node from the end.
Any "next state" rule is a list: Happy Number and Find the Duplicate Number are Floyd on numbers and on array indices.

the weight it carries

Illustrative: 10 lakh nodes whose last 1 lakh form a loop. A HashSet of visited nodes stores up to 1,000,000 references. Floyd stores 2: slow reaches the loop after 900,000 steps, and fast catches it within one more lap (≤ 100,000 steps) — at most 1,000,000 slow steps in total.

without it

Cycle and middle questions would need O(n) memory (a set or an array of nodes) — impossible when the "list" is a huge generated sequence.

when · why · how

when: Detect a loop, find where it starts, find the middle, or the n-th node from the end — on a list or on any x → f(x) sequence.
why: O(n) time and O(1) space: inside a loop fast gains exactly one node per step, so it can never jump over slow.
how: while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) … } — compare nodes with == (identity), not values.

since2002 (Java 1.4)

Doubly linked list + HashMap (the LRU cache)

Josh Bloch (author of java.util.LinkedList and LinkedHashMap)

Java 1.2 (1998) shipped LinkedList, a doubly linked list, in the new Collections Framework. Java 1.4 (2002) added LinkedHashMap: a HashMap with a doubly linked list running through all of its entries. Its Javadoc says plainly that, in access order, it is "well-suited to building LRU caches" — the very design LC 146 asks you to build by hand. Doubly linked lists themselves have no single recorded inventor; this is where Java made the pairing a library class.

the problem it solvedO(1) lookup and O(1) reordering at the same time — exactly what an LRU cache needs to stay fast as it grows.

its jobs today

LRU caches: the map finds the entry, the list keeps recency — new LinkedHashMap<>(16, 0.75f, true) plus removeEldestEntry is a complete LRU cache in a few lines.
O(1) removal of a node you already hold, because it knows both neighbours: LRU eviction, LFU buckets, ListIterator.remove() on a LinkedList.
Two-way stepping: back/forward histories and deques can move either way from any node.

the weight it carries

Illustrative: an LRU cache of 10 lakh entries doing 1,000 evictions a second. With a doubly linked list each eviction is 1 unlink (2 reference writes) + 1 map removal. Scanning for the oldest timestamp instead costs up to 1,000,000 comparisons per eviction — 10⁹ comparisons every second.

without it

Moving or evicting an entry by recency would need an O(n) search, so a cache would slow down exactly as it grows.

when · why · how

when: "O(1) get and put", "evict the least recently used", or any time you must delete a node you are already holding.
why: With prev stored, unlinking is O(1) — no walk to find the predecessor. The cost is one extra reference per node.
how: By hand: Node { key, value, prev, next } between two sentinels, plus a HashMap<Integer, Node>. Library: LinkedHashMap with accessOrder = true and removeEldestEntry.

02 · plain english

The idea in 30 seconds

A linked list is a chain of nodes. Each node holds a value and a reference (next) to the node after it.

Nodes live anywhere in memory. Only the references hold the order — so inserting or deleting is just rewiring arrows, O(1) once you are at the spot.

The price: no indexes. To reach the 5th node you must walk 4 hops from head — O(n).

picture this

A web series where every episode page has only a Next episode link. Slipping a bonus episode in after episode 3 means changing one link. But to reach episode 7 from the start, you click Next six times — there is no "jump to 7".

03 · remember

What you must know

A node is val + next. The list itself is just a reference to the first node, head. The last node's next is null.
Singly linked: one next. Doubly linked: prev + next, so you can remove a node you hold in O(1). Circular: the tail points back to the head.
Insert / delete is O(1) if you already hold the node before the spot. Finding that spot is O(n). Access by index is O(n) — the opposite trade-off from arrays.
Dummy head trick: put a fake node before head. Every real node now has a predecessor, so "change the head" stops being a special case. Return dummy.next.
Slow / fast pointers: fast moves 2, slow moves 1. Finds the middle, detects a cycle (Floyd), and finds the cycle's entry — all in O(1) space.
Order of rewiring matters: save curr.next before you overwrite it, or the rest of the list is lost forever.
Any "next" rule is a linked list: i → nums[i] turns an array into a chain, so Floyd can find a repeated value without extra memory (LC 287).
In Java, a node nobody references is garbage-collected — "deleting" means making it unreachable.
java.util.LinkedList is doubly linked. For interview problems you almost always write your own tiny ListNode; for a stack or queue, prefer ArrayDeque.

04 · see it

Play with it in 3D

Press Space to play, ←/→ to step, drag to move, ? for all shortcuts. Try your own input.

sim

Insert at a position

Walk `prev` to the node before the spot, then change exactly two references. The order of the two changes matters.

loading simulation…

javajava.util.*

1class Insert {2    /** Inserts val so it ends up at position index (0 = new head). Past the end → append. */3    static ListNode insertAt(ListNode head, int index, int val) {4        ListNode dummy = new ListNode(0, head);5        ListNode prev = dummy;6        for (int i = 0; i < index && prev.next != null; i++) {7            prev = prev.next;8        }9        ListNode node = new ListNode(val);10        node.next = prev.next;11        prev.next = node;12        return dummy.next;13    }14}

sim

Delete by value with a dummy head

Deleting = skipping. The removed node drops away because nothing points to it any more.

loading simulation…

javajava.util.*

1class Remove {2    /** Removes every node whose value equals val (LeetCode 203). */3    static ListNode removeAll(ListNode head, int val) {4        ListNode dummy = new ListNode(0, head);5        ListNode prev = dummy;6        while (prev.next != null) {7            if (prev.next.val == val) {8                prev.next = prev.next.next;9            } else {10                prev = prev.next;11            }12        }13        return dummy.next;14    }15}

sim

Reverse — flip one arrow per step

`prev`, `curr`, `next`: save, flip, advance. The green part is already reversed.

loading simulation…

javajava.util.*

1class Solution {2    public ListNode reverseList(ListNode head) {3        ListNode prev = null, curr = head;4        while (curr != null) {5            ListNode next = curr.next;6            curr.next = prev;7            prev = curr;8            curr = next;9        }10        return prev;11    }12}

sim

Floyd's cycle detection

Set `pos` to make the tail loop back (−1 = no loop). Inside a loop, fast gains one node per step, so it must catch slow.

loading simulation…

javajava.util.*

1class Solution {2    public boolean hasCycle(ListNode head) {3        ListNode slow = head, fast = head;4        while (fast != null && fast.next != null) {5            slow = slow.next;6            fast = fast.next.next;7            if (slow == fast) return true;8        }9        return false;10    }11}

sim

Find the middle in one pass

When fast has run the whole list, slow has run half of it.

loading simulation…

javajava.util.*

1class Solution {2    public ListNode middleNode(ListNode head) {3        ListNode slow = head, fast = head;4        while (fast != null && fast.next != null) {5            slow = slow.next;6            fast = fast.next.next;7        }8        return slow;9    }10}

sim

Merge two sorted lists

Nodes are not copied — `tail.next` re-links them onto the bottom row one by one.

loading simulation…

javajava.util.*

1class Solution {2    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {3        ListNode dummy = new ListNode();4        ListNode tail = dummy;5        while (list1 != null && list2 != null) {6            if (list1.val <= list2.val) {7                tail.next = list1;8                list1 = list1.next;9            } else {10                tail.next = list2;11                list2 = list2.next;12            }13            tail = tail.next;14        }15        tail.next = (list1 != null) ? list1 : list2;16        return dummy.next;17    }18}

sim

A doubly linked list at work: the LRU cache

Top: the HashMap's keys. Bottom: the list between two sentinels, most recent first. Every get and put is a lookup plus a few arrow changes.

loading simulation…

javaclass LRUCachejava.util.* · java.util.function.*

1class LRUCache {2    private static class Node {3        int key, value;4        Node prev, next;5        Node(int key, int value) { this.key = key; this.value = value; }6    }7 8    private final int capacity;9    private final Map<Integer, Node> map = new HashMap<>();          // key → node, O(1) lookup10    private final Node head = new Node(0, 0), tail = new Node(0, 0); // sentinels; head.next = most recent11 12    public LRUCache(int capacity) {13        this.capacity = capacity;14        head.next = tail;15        tail.prev = head;16    }17 18    public int get(int key) {19        Node node = map.get(key);20        if (node == null) return -1;21        unlink(node);22        addFront(node); // touched → most recently used23        return node.value;24    }25 26    public void put(int key, int value) {27        Node node = map.get(key);28        if (node != null) {           // update + refresh29            node.value = value;30            unlink(node);31            addFront(node);32            return;33        }34        if (map.size() == capacity) { // full → evict the node just before tail35            Node lru = tail.prev;36            unlink(lru);37            map.remove(lru.key);      // why each node stores its key38        }39        node = new Node(key, value);40        map.put(key, node);41        addFront(node);42    }43 44    private void unlink(Node x) {45        x.prev.next = x.next;46        x.next.prev = x.prev;47    }48 49    private void addFront(Node x) {50        x.next = head.next;51        x.prev = head;52        head.next.prev = x;53        head.next = x;54    }55}

05 · cost

Time & space, explained

Linked list vs array list
	Singly linked	Doubly linked	ArrayList	why
Get the k-th element	O(n)	O(n)	O(1)	A list has no addresses to compute — you hop k times. An array computes `base + k × size` directly.
Insert / delete at head	O(1)	O(1)	O(n)	The list rewires one or two references. The array must shift every element one slot.
Insert at tail	O(1)*	O(1)	O(1) amortized	*Only if you keep a `tail` reference. ArrayList appends in O(1) except an occasional O(n) resize.
Delete at tail	O(n)	O(1)	O(1)	Singly linked must walk to the second-to-last node to set its `next = null`. Doubly linked has `tail.prev`.
Insert / delete next to a node you hold	O(1)	O(1)	O(n)	Just rewire. Singly linked can only cheaply delete the node after the one you hold; doubly linked can delete the node itself.
Search by value	O(n)	O(n)	O(n)	No order to exploit — check elements one by one (binary search doesn't work on lists: no O(1) middle).
Extra memory per element	1 reference + object header	2 references + object header	1 slot (amortized)	Every node is a separate object. Arrays store values side by side, which is also far friendlier to the CPU cache.

The core techniques
	Time	Extra space	why
Reverse (iterative)	O(n)	O(1)	Each node's arrow is flipped once with three references.
Reverse (recursive)	O(n)	O(n)	Same work, but n stack frames — can overflow on long lists.
Reverse a section / k at a time	O(n)	O(1)	Each node is flipped once; finding each block's k-th node adds one more walk over it.
Find middle (slow / fast)	O(n)	O(1)	fast walks the list once; slow walks half.
Cycle detection (Floyd)	O(n)	O(1)	slow enters the cycle within n steps; fast then closes the gap one node per step.
Cycle detection (HashSet)	O(n)	O(n)	Stores every visited node.
Merge two sorted lists	O(n + m)	O(1)	Each step re-links one node; nothing is copied.
Palindrome check (middle + reverse + compare)	O(n)	O(1)	A few linear passes; the second half is reversed in place and restored.
Rotate by k	O(n)	O(1)	One pass counts the nodes and finds the tail; `k % n` drops whole laps, so at most one more pass reaches the cut.

06 · java

Raw vs Collections Framework

The node — the only class you need

javaListNode (LeetCode's definition)java.util.*

1class ListNode {2    int val;        // the data3    ListNode next;  // reference to the next node (null at the end)4 5    ListNode() {}6    ListNode(int val) { this.val = val; }7    ListNode(int val, ListNode next) { this.val = val; this.next = next; }8}

LeetCode gives you this class. next holds a reference (an arrow), not a copy of the next node.
A list is just ListNode head. An empty list is head == null — check for it first in every problem.
== on nodes compares identity (same object). That is exactly what you want for cycles and intersections.

Doubly linked: build it vs use java.util.LinkedList

javahand-written with sentinelsjava.util.*

1class DoublyLinkedList {2    static class Node {3        int val;4        Node prev, next;5        Node(int val) { this.val = val; }6    }7 8    // Two sentinels: the list is never "empty" internally, so no null checks.9    private final Node head = new Node(0), tail = new Node(0);10    private int size;11 12    DoublyLinkedList() {13        head.next = tail;14        tail.prev = head;15    }16 17    Node addFirst(int val) { return insertAfter(head, new Node(val)); } // O(1)18    Node addLast(int val) { return insertAfter(tail.prev, new Node(val)); } // O(1)19 20    private Node insertAfter(Node p, Node x) {21        x.prev = p;22        x.next = p.next;23        p.next.prev = x;24        p.next = x;25        size++;26        return x;27    }28 29    /** O(1) — we already hold the node, and it knows both neighbours. */30    void remove(Node x) {31        x.prev.next = x.next;32        x.next.prev = x.prev;33        size--;34    }35 36    int removeLast() {37        if (size == 0) throw new NoSuchElementException();38        Node x = tail.prev;39        remove(x);40        return x.val;41    }42 43    int size() { return size; }44 45    List<Integer> toList() {46        List<Integer> out = new ArrayList<>();47        for (Node p = head.next; p != tail; p = p.next) out.add(p.val);48        return out;49    }50}

javaLinkedList / ArrayDequejava.util.*

1class Library {2    static List<Integer> demo() {3        LinkedList<Integer> list = new LinkedList<>(List.of(2, 3)); // doubly linked4        list.addFirst(1);   // O(1)            → [1, 2, 3]5        list.addLast(4);    // O(1)            → [1, 2, 3, 4]6        list.removeFirst(); // O(1)            → [2, 3, 4]7        list.add(1, 9);     // O(n): walks to index 1 → [2, 9, 3, 4]8        ListIterator<Integer> it = list.listIterator();9        while (it.hasNext()) {10            if (it.next() == 3) it.remove(); // O(1) at the cursor → [2, 9, 4]11        }12        return list;13    }14 15    static Deque<Integer> asDeque() {16        Deque<Integer> dq = new ArrayDeque<>(); // usually faster than LinkedList for stack/queue use17        dq.offerLast(1);18        dq.offerLast(2);19        dq.offerFirst(0);   // → [0, 1, 2]20        dq.pollLast();      // → [0, 1]21        return dq;22    }23}

Two sentinel nodes (head, tail) that are never removed mean insertAfter and remove never check for null.
Removing a node you hold is O(1) in a doubly linked list. LinkedList hides its nodes, so you only get that via a ListIterator.
list.get(i) on a LinkedList walks from the nearer end: O(n). Calling it in a loop is a hidden O(n²).
For a stack or queue, the Java docs recommend ArrayDeque: it is usually faster than LinkedList (no node objects, better cache use).
Interviews that say "design" (LRU cache, browser history) want the hand-written doubly linked list — that is the whole point of the question.

Java API you will actually use
call	does	cost
`list.addFirst(x) / addLast(x)`	Insert at either end (LinkedList is a Deque)	O(1)
`list.removeFirst() / removeLast()`	Remove at either end; throws if empty	O(1)
`list.peekFirst() / pollFirst()`	Look at / remove the head; return null if empty	O(1)
`list.get(i) / list.set(i, x)`	Walks from the nearer end to index i	O(n)
`list.add(i, x) / list.remove(i)`	Walk to i, then rewire	O(n)
`list.contains(x) / remove(Object)`	Linear search by equals()	O(n)
`listIterator().add(x) / .remove()`	Insert / delete at the iterator's cursor	O(1)
`new ArrayDeque<>()`	Array-backed deque: the default stack / queue	O(1) amortized ops
`new LinkedHashMap<>(16, 0.75f, true)`	HashMap + doubly linked list in access order (LRU)	O(1) average

A LeetCode linked-list problem

→ Your own ListNode + references

The problem gives you nodes; the skill tested is rewiring them.

A stack or a queue

→ ArrayDeque

O(1) at both ends, less memory and faster than LinkedList.

Indexed reads in a loop

→ ArrayList

O(1) get(i); LinkedList would be O(n) per read.

Many inserts/removals while iterating

→ LinkedList + ListIterator

O(1) at the cursor; ArrayList shifts O(n) per change.

O(1) lookup and O(1) reordering (LRU)

→ HashMap + doubly linked list (or LinkedHashMap)

The map finds the node; the list keeps the order.

07 · recognise

Spot the pattern

"Middle of the list", "split in half", "palindrome list"

slow / fast pointers (fast moves 2)

"Cycle", "loop", "where does the loop start"

Floyd's tortoise and hare (then reset one pointer to head)

"n-th from the end" in one pass

Two pointers with a fixed gap of n

The head might change (delete head, merge, partition)

Dummy head node — return dummy.next

"Reverse" all or part of a list, "reorder", "k-group"

prev / curr / next rewiring

Two sorted lists → one sorted list

Merge with dummy + tail (merge-sort step)

Split by a rule but keep the order (odd/even positions, < x vs ≥ x)

Two dummy-headed chains, then join — and end the second with null

"Rotate the list by k" with a huge k

Count n, use k % n, close into a ring, cut once

n + 1 values in 1..n, find the repeat, O(1) space, don't modify

Treat i → nums[i] as a linked list; Floyd finds the cycle's entry

"O(1) get and put", "most recently used"

HashMap + doubly linked list (LRU)

Deep copy with extra pointers

HashMap old → new, or interleave copies to get O(1) space

08 · traps & tricks

Mistakes to avoid, tricks to use

traps

Overwriting curr.next before saving it — the rest of the list becomes unreachable.
Dereferencing null: fast.next.next needs fast != null && fast.next != null checked first, in that order.
Forgetting to set the new tail's next = null (after reversing with a stack, reordering, splitting) — creates an accidental cycle.
Returning head when the head itself was deleted or moved — return dummy.next instead.
Comparing node values when the problem needs node identity (cycles, intersections): use == on nodes.
Calling LinkedList.get(i) inside a loop: each call walks the list, so the loop is O(n²).
Losing the original head because you moved head itself while walking — walk with a separate curr.
Using k as given when it can be far larger than the length (Rotate List): reduce it with k % n — after checking the list isn't empty.
Recursion on lists of 10⁴–10⁵ nodes can throw StackOverflowError; prefer the iterative version.

tricks

Draw boxes and arrows for 3 nodes before coding. Re-draw after each line you write. Most bugs show up on paper.
Say your invariants out loud: "prev is the head of the reversed part; curr is the first unreversed node."
Default to a dummy head whenever the first node could change — it costs one line and removes a whole class of bugs.
Test every list solution on: empty list, one node, two nodes, odd and even length, and the target at the head and at the tail.
Many hard list problems are combos: Reorder List = find middle + reverse + merge; Palindrome = find middle + reverse + compare; k-group = reverse a block, repeat. Learn the moves cold.
In an interview, state up front whether you may modify the input list — it changes which solution is allowed.

09 · why & how

Questions you might be too shy to ask

If linked lists are slower to index, why do they exist at all?

Because inserting or deleting in the middle is O(1) once you're there — no shifting. That is why they power LRU caches, hash-table chains and memory free lists. In everyday Java code, though, ArrayList and ArrayDeque usually win because arrays are cache-friendly.

When I write curr = curr.next, am I changing the list?

No. curr is just a local arrow. Moving it changes where you are looking, not the list. The list changes only when you assign to a field: curr.next = something. So walking with curr is safe, but curr.next = null cuts the list right there. Bas itna yaad rakho: x = … moves a pointer, x.next = … rewires the list.

What does dummy actually buy me?

Every real node gets a node in front of it, so "insert before the head" and "delete the head" use the same code as any other position. Without it you need if (head == null) and if (target == head) branches — the classic source of bugs.

Should my loop be while (curr != null) or while (curr.next != null)?

Ask where the loop must stop. curr != null visits every node, then curr ends as null — use it to print, count, or reverse. curr.next != null stops on the last node — use it to find the tail (Rotate List) or when the body reads curr.next.val. The second one crashes on an empty list, so check head == null first.

Which middle does slow land on, and which loop condition should I use?

On [1, 2, 3, 4] there are two middles, 2 and 3. while (fast != null && fast.next != null) stops slow on the second middle (3) — that is what LC 876 wants. while (fast.next != null && fast.next.next != null) stops slow on the first middle (2) — use it to split a list in half (Palindrome, Reorder List, merge sort), because the first half then ends at slow. It reads fast.next straight away, so check head == null first. Odd lengths give the same single middle with both.

Why does Floyd's algorithm always meet, and why can't fast jump over slow?

Once both are in the loop, fast gains exactly one node on slow each step (2 − 1). The gap shrinks 3, 2, 1, 0 — it can't skip from 1 to −1. So they meet within one lap, and the whole run is O(n).

Why does resetting one pointer to head find the cycle's start?

Let a = steps from head to the entry and b = steps from the entry to the meeting point. slow walked a + b, fast walked twice that, and the difference a + b is a whole number of laps. So walking a more steps from the meeting point lands exactly on the entry — the same a steps a pointer from head needs.

How can an array (LC 287) have a "cycle"?

Read index i as a node whose next is nums[i]. Every node has exactly one arrow out, and there are finitely many nodes, so a walk from index 0 must eventually repeat — that's a loop. The value stored at two indices has two arrows coming in, so it is where the loop is entered.

Do I need to free memory when I delete a node in Java?

No. Once nothing references a node, the garbage collector reclaims it. Your only job is to make it unreachable by rewiring next (and prev). In C/C++ you'd call free/delete.

Can I just swap the values instead of moving nodes?

Sometimes it passes, but it dodges the skill being tested, and several problems forbid it ("you may not modify the values" in Reorder List and k-Group). Real nodes often carry more than an int, so moving the node is the honest answer. Say this out loud if you're tempted.

For LRU Cache, why a doubly linked list? Wouldn't a singly linked one work?

To unlink a node you must change the next of the node before it. The HashMap hands you the node itself. With prev you reach its neighbour in one step, so unlinking is O(1). With only next you would walk from the head to find the node before it — O(n), and the O(1) promise breaks.

Should I use java.util.LinkedList in interviews?

Rarely. For list problems, you're given ListNode and must rewire it yourself. For stacks/queues, ArrayDeque is better. Use LinkedList only when you truly need cheap insert/remove at an iterator position.

Iterative or recursive reversal?

Iterative is O(1) space and can't overflow the stack — lead with it. Know the recursive version too: interviewers often ask for it as a follow-up to check you understand head.next.next = head.

I follow the reversal when I read it, but my own code keeps losing nodes. How do I practise?

Make a small table with columns prev, curr, next and fill one row per loop step for [1, 2, 3]. Chalo, dry-run karte hain — on paper, not in your head. Then step the reverse sim and check that every row matches yours. Write the four lines (save, flip, move prev, move curr) from memory once a day for a week. After that, Reverse Linked List II and k-Group are the same four lines with a hook at each end.

10 · practice

Interview problems

Every problem has brute → better → optimal solutions in Java, with complexity and a dry run. show patterns & complexity

#206
Reverse Linked Listmust-do
EasyAdobeAppleMicrosoftBloombergOracle+1
#21
Merge Two Sorted Listsmust-do
EasyBloombergAmazonMicrosoftGoogleApple+1
#876
Middle of the Linked List
EasyWalmartAmazonMicrosoftApple
#141
Linked List Cyclemust-do
EasyBloombergMicrosoftAmazonGoogleMeta
#234
Palindrome Linked Listmust-do
EasyAmazonMetaMicrosoft
#19
Remove Nth Node From End of Listmust-do
MediumMetaMicrosoftAmazonBloombergApple+1
#142
Linked List Cycle IImust-do
MediumMicrosoftAmazonBloombergGoogle
#287
Find the Duplicate Numbermust-do
MediumNVIDIAAmazonBloombergGoogleMicrosoft
#92
Reverse Linked List II
MediumAmazonMicrosoftMeta
#328
Odd Even Linked List
MediumAmazonMicrosoft
#86
Partition List
MediumAmazonMicrosoft
#82
Remove Duplicates from Sorted List II
MediumBloombergMicrosoftAmazon
#61
Rotate List
MediumBloombergAmazonMicrosoft
#143
Reorder Listmust-do
MediumAmazonMicrosoftMeta
#2
Add Two Numbersmust-do
MediumAdobeBloombergMicrosoftAmazonGoogle+1
#138
Copy List with Random Pointer
MediumMetaAmazonNVIDIAMicrosoftBloomberg+1
#25
Reverse Nodes in k-Groupmust-do
HardMicrosoftAmazonGoogleMeta
#146
LRU Cachemust-do
MediumAppleOracleSamsungByteDance / TikTokWalmart+1

Also practise this here

Each problem has one home page in the course; these use this chapter's idea too. The note says what to look for.

#24
Swap Nodes in Pairs
Mediumin Recursion
Reverse Nodes in k-Group with k = 2 — a good warm-up before LC 25.
#23
Merge k Sorted Lists
Hardin Heaps
This chapter's merge, run on k lists at once with a min-heap of the current heads.
#148
Sort List
Mediumin Sorting
Merge sort on a linked list: split with slow/fast, sort both halves, merge — three moves from this chapter.
#707
Design Linked List
Mediumin Java OOP
Build the list class yourself: get, addAtHead, addAtTail, addAtIndex and deleteAtIndex with a dummy head.

11 · revise

The whole chapter on one screen

10 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

what it is
A chain of nodes: each holds val and a next reference, and the list is just head. Splicing is O(1) once you're there; reaching the k-th node is O(k).
use it when
Inserts and deletes next to nodes you hold, LRU caches, hash chains — and every interview problem that hands you a ListNode.
template
Dummy head: ListNode dummy = new ListNode(0, head); walk with prev, then return dummy.next; — no special case when the head changes.
template
Reverse: next = curr.next; curr.next = prev; prev = curr; curr = next; then return prev. Save before you flip.
template
Slow/fast: while (fast != null && fast.next != null) → middle (2nd), cycle (they meet), n-th from end (gap of n + 1).
cost
Index O(n) · splice O(1) once there · reverse / middle / cycle O(n) time, O(1) space · recursion over a list = O(n) stack.
trap
Overwriting curr.next before saving it loses the rest of the list. Forgetting tail.next = null after splitting creates a cycle.
trap
Cycles need node identity (==), not equal values. And fast.next.next needs fast != null && fast.next != null checked first.
pro tip
Hard list problems are combos: Reorder = middle + reverse + merge · Palindrome = middle + reverse + compare · k-group = reverse a block, repeat.
pro tip
O(1) get and put with recency → HashMap + doubly linked list (or LinkedHashMap in access order).

12 · recall

Flip, remember, repeat

card 1 / 14

recall

Why put a dummy node in front of head?

tap or Space to flip ↻

Question 1: Why put a dummy node in front of head?

13 · check yourself

Quick quiz

You hold a reference to a node in a singly linked list. Which operation is O(1)?
In iterative reversal, why must `next = curr.next` come before `curr.next = prev`?
What does a dummy head node save you from?
Floyd's algorithm: inside a cycle, how much does fast gain on slow each step?
List [1,2,3,4,5,6]. slow/fast with `while (fast != null && fast.next != null)` — where does slow stop?
Why does an LRU cache need a *doubly* linked list?
`LinkedList<Integer> list` has n elements. What does `for (int i = 0; i < n; i++) list.get(i);` cost?
Reverse Nodes in k-Group on [1,2,3,4,5] with k = 3. What is the result?
Find the Duplicate Number as a linked list (i → nums[i]): which index is the head of the walk?

0/0 correct · 9 left

14 · learn more