Knowledge Guide
Home › DSA

Linked List

Step 9 in the DSA path · 7 concepts · 9 problems

0 / 16 complete

📘 Learn Linked List from zero

The Linked List reversal pattern walks a list one node at a time, flipping each next pointer to point backward while keeping a handle on the rest of the list so you never lose it. It uses three pointers — prev, curr, and a saved next — and runs in O(n) time with O(1) extra space. Reach for it whenever a problem says "reverse," "flip direction," or asks you to rewire links in place: it is the engine behind Reverse Linked List II, Reverse Nodes in k-Group, and palindrome checks. The trigger: you must change the direction of pointers without allocating a new list.

✨ Added by the guide to build intuition — not from the source course.

🏗️ Visual walkthrough — trace it step by step

Step 1 — Setup pointers
list:  1 -> 2 -> 3 -> 4 -> NULL

prev = NULL
curr ----+
         v
         1 -> 2 -> 3 -> 4 -> NULL

We start with prev = NULL (the new tail-to-be) and curr at the head node 1. Why safe: we have not touched any pointer yet, so the original list 1->2->3->4 is fully intact.

Step 2 — Flip node 1
nxt = curr.next   (saves 2 before we cut)

        prev   curr   nxt
         |      |      |
         v      v      v
NULL <-- 1      2 ->  3 -> 4 -> NULL

then advance:  prev=1, curr=2

Save nxt = 2, then set curr.next = prev so node 1 now points to NULL. Why safe: we captured nxt before overwriting curr.next, so the rest of the list (2->3->4) is never orphaned.

Step 3 — Flip node 2
reversed-so-far: 1 -> NULL
remaining:       2 -> 3 -> 4 -> NULL

save nxt=3, set 2.next = 1

NULL <- 1 <- 2      3 -> 4 -> NULL
        prev=2      curr=3

Save nxt = 3, point node 2 back at node 1, then advance prev=2, curr=3. Why safe: prev always holds a valid, fully-reversed sub-list (2->1->NULL), and nxt still holds the untouched tail.

Step 4 — Flip node 3
reversed-so-far: 2 -> 1 -> NULL
remaining:       3 -> 4 -> NULL

save nxt=4, set 3.next = 2

NULL <- 1 <- 2 <- 3      4 -> NULL
             prev=3      curr=4

Save nxt = 4, point node 3 back at node 2, advance prev=3, curr=4. Why safe: the invariant holds — everything left of curr is correctly reversed, everything from curr rightward is still the original forward chain.

Step 5 — Flip node 4 (last)
reversed-so-far: 3 -> 2 -> 1 -> NULL
remaining:       4 -> NULL

save nxt=NULL, set 4.next = 3

NULL <- 1 <- 2 <- 3 <- 4      NULL
                  prev=4      curr=NULL

Save nxt = NULL, point node 4 back at node 3, advance prev=4, curr=NULL. Why safe: nxt legitimately became NULL (node 4 was the original tail), so advancing curr to NULL is the natural loop exit.

Step 6 — Loop ends, return prev
curr == NULL  ->  stop the loop

new list (head = prev = 4):
4 -> 3 -> 2 -> 1 -> NULL
^
prev (new head)

The loop condition while curr != NULL is now false, so we stop and return prev, which points at node 4 — the new head. Why safe: every next pointer was rewired exactly once, no node was lost or duplicated, giving the fully reversed 4->3->2->1->NULL in O(n)/O(1).

🎯 Guided practice

Problem 1 (easy) — Reverse a singly linked list. Input 1→2→3→null, output 3→2→1→null. Core pattern: iterative three-pointer relink.

  1. Keep two pointers: prev = null and curr = head. prev is the already-reversed part; curr is what's left.
  2. Loop while curr != null. First save the link you're about to destroy: next = curr.next.
  3. Flip the arrow: curr.next = prev (point backward).
  4. March both pointers forward: prev = curr, then curr = next.
  5. When curr hits null, prev is the new head — return it. Trace: prev goes null → 1 → 2→1 → 3→2→1. O(n) time, O(1) space.

The reusable lesson: always stash next before overwriting curr.next, or you orphan the tail.

Problem 2 (medium) — Swap Nodes in Pairs. Input 1→2→3→4, output 2→1→4→3. Swap adjacent nodes by relinking, not by swapping values. Core pattern: dummy head + careful pointer surgery.

  1. Create dummy with dummy.next = head; let prev = dummy. Using a dummy means swapping the original first pair needs no special case.
  2. Loop while prev.next and prev.next.next both exist (you need a full pair; an odd trailing node is left in place). Name them: first = prev.next, second = prev.next.next.
  3. Rewire three arrows in order: first.next = second.next (first jumps past the pair), second.next = first (second now precedes first), prev.next = second (link the prior segment to the new front).
  4. Advance: prev = first (first is now the tail of this swapped pair), continue.
  5. Return dummy.next — never the stale head. O(n) time, O(1) space.

Why it generalizes: dummy-head + "name the nodes, then relink in a fixed safe order" is the same skeleton behind Reverse Linked List II and Reverse Nodes in k-Group — only the group size and the boundary bookkeeping (count k nodes first; leave a partial final group untouched) change.

✨ Added by the guide — work these before the full problem set.

Lessons in this topic