Linked Lists

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

1. ◆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).

   #1
2. ↯use it when

   Inserts and deletes next to nodes you hold, LRU caches, hash chains — and every interview problem that hands you a ListNode.

   #2
3. { }template

   Dummy head: ListNode dummy = new ListNode(0, head); walk with prev, then return dummy.next; — no special case when the head changes.

   #3
4. { }template

   Reverse: next = curr.next; curr.next = prev; prev = curr; curr = next; then return prev. Save before you flip.

   #4
5. { }template

   Slow/fast: while (fast != null && fast.next != null) → middle (2nd), cycle (they meet), n-th from end (gap of n + 1).

   #5
6. O( )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.

   #6
7. !trap

   Overwriting curr.next before saving it loses the rest of the list. Forgetting tail.next = null after splitting creates a cycle.

   #7
8. !trap

   Cycles need node identity (==), not equal values. And fast.next.next needs fast != null && fast.next != null checked first.

   #8
9. ✦pro tip

   Hard list problems are combos: Reorder = middle + reverse + merge · Palindrome = middle + reverse + compare · k-group = reverse a block, repeat.

   #9
10. ✦pro tip

    O(1) get and put with recency → HashMap + doubly linked list (or LinkedHashMap in access order).

    #10

Shaky on a card? Open the chapter or flip its recall cards.