</> MAANG.io
Sign in
Level101201301
coding interview · 101

Foundations

Master coding interviews with comprehensive coverage of data structures, algorithms, and problem-solving techniques. Progress from fundamentals to advanced topics with expertly curated content.

0/255 solved 0% complete

List Fundamentals

What is this?

A linked list is a chain of nodes, where each node points to the next one — think of a treasure hunt where each clue leads you to the following clue. The fundamentals are the basic hands-on moves for working with that chain: flipping all the arrows to run it backwards, building a brand-new chain as you walk, and rearranging the nodes in place.

flowchart TD A["List Fundamentals"] --> B["Reverse the List"] B --> C["Build a New List"] C --> D["Reorder in Place"]

💡 Fun fact: Reversing a linked list is one of the most-asked coding interview questions of all time, yet the clean iterative solution needs only three pointer variables and a single pass through the list.

🔓 The 3 problems in this chapter are free. Sign in with Google or Microsoft to start solving.

Core idea: Everything you'll ever do to a linked list is re-pointing next fields, in order, without losing the rest of the chain. This chapter drills the three moves that underpin the whole topic: reverse it, build a new one as you walk, and restructure it in place.

The two habits that prevent every bug

Reversing 1 -> 2 -> 3: save nxt = curr.next so the rest is not orphaned, flip the arrow with curr.next = prev, then step forward with prev = curr; curr = nxt

  1. Cache next before you overwrite it. A node has exactly one forward pointer; the instant you rewrite it, the rest of the list is gone unless you saved it.
  2. Use a dummy head. A fake node sitting before head means "edit/insert/delete at the front" stops being a special case — you always have a prev to splice from.

Master those and pointer surgery becomes mechanical.

The three problems

Tree of the three problems: List Fundamentals branches into Reverse Linked List (re-point backward), Add Two Numbers (build new list + carry), and Reorder List (compose: middle+reverse+merge)

  • Reverse Linked List — the keystone. Walk once, flipping each next to point at the previous node (cache-next first). O(n) time, O(1) space. Reorder and many later problems reuse this exact routine.
  • Add Two Numbers — two digit-lists (least-significant first); walk both, sum digit + carry, append to a new list built behind a dummy head. The reverse digit order is why you can add left-to-right.
  • Reorder List — L0→Ln→L1→Ln-1→… in place. Not one trick but three composed: find the middle (fast/slow), reverse the second half, merge the two halves alternately.

The moves this chapter teaches

Move Mechanic Reused in
Cache-next reverse save next, flip pointer, advance Reverse, Reorder
Dummy head + tail build append to a fake-headed list Add Two Numbers
Carry propagation digit, carry = divmod(a+b+carry, 10) Add Two Numbers
Compose primitives middle → reverse → merge Reorder

The progression is deliberate: Reverse teaches the atomic move, Add Two Numbers teaches building + dummy head, and Reorder shows that hard list problems are usually two or three easy ones glued together.

📓 Draw it yourself

  1. Reverse, arrow by arrow. Draw 1→2→3, then redraw it 3 times flipping one arrow per step with prev/curr/next labels.
  2. Fold the tail onto the head. Write 1 2 3 4 5 6 on a paper strip and fold it so 6 lands under 1, 5 under 2 — that's Reorder.

Snap photos and embed them with the /host-diagrams skill.

Key takeaways

  • Pointer surgery, two rules: cache next before rewiring; use a dummy head for front edits.
  • Reverse Linked List is the keystone — internalize it; it recurs everywhere.
  • Build with a dummy head + carry for "construct a new list" problems (Add Two Numbers).
  • Hard list problems decompose — Reorder = find-middle + reverse + merge.
  • Why it matters: these are the precision drills every harder list (and many tree/stream) problems are built from.

Order: Reverse Linked List → Add Two Numbers → Reorder List.

Core idea: Reversing a singly linked list is nothing but re-pointing each node's next arrow backward — and the only trick is caching the next node before you overwrite the pointer that would have led you to it.

Problem, rephrased

Picture a music player with a "play history" stored as a singly linked list. Each song points forward to the song you played after it: Intro → Verse → Chorus → Bridge → Outro. You only ever kept forward links to save memory. Now the user hits "replay in reverse order", so you need the chain flipped to Outro → Bridge → Chorus → Verse → Intro — and you must return a handle to the new first song (Outro), because the player always starts from a single head pointer.

Formally: given the head of a singly linked list, reverse the direction of every link and return the new head (the old tail). We must do this in place — no building a fresh list, no array detour.

Input (head → … → tail) Output (new head → … → new tail)
1 → 2 → 3 → 4 → 5 5 → 4 → 3 → 2 → 1
7 → 9 9 → 7
42 (single node) 42
empty (None) empty (None)

Sign in to continue reading

The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.

Sign in to read the full lesson

Sign in to MAANG.io

Use your Google or Microsoft account — no password to remember.

Continue with Google Continue with Microsoft

Please accept the terms above to continue.