</> 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.

Reorder List

Core idea: The reorder is just the front half interleaved with the reversed back half — so split the list at the middle, reverse the second half, and zip the two halves together node by node.

Problem, rephrased

Imagine you're seating guests around a long dinner table from a single waiting line. The line is in order of arrival: guest 0 arrived first, guest n arrived last. You want to seat them so each early-arriving guest is paired with a late-arriving one — first with last, second with second-to-last, and so on — alternating down the line until they meet in the middle. The earliest guest still leads, the latest guest comes next, then the second-earliest, then the second-latest.

Concretely: you're given a singly linked list L0 → L1 → … → Ln-1 → Ln. Rearrange the nodes (not their values) into the order L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …. Do it in place, using O(1) extra space, and re-link nodes rather than copying or swapping their values.

Input list Output list Why
1 → 2 → 3 → 4 1 → 4 → 2 → 3 First with last, then the inner pair
1 → 2 → 3 → 4 → 5 1 → 5 → 2 → 4 → 3 Odd length: the middle node 3 lands last, alone
1 → 2 1 → 2 Two nodes are already in reorder form
7 7 A single node has nothing to interleave

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.