CMD Guide
Home › DSA

Linked List

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

0 / 13 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

🧠 Review & recall

Active recall is what moves a topic into long-term memory. Flip each card before revealing, then test yourself — your results are saved on this device.

Flashcard
What is the core mechanic of iteratively reversing a singly linked list, and what are its time and space complexities?
tap to reveal →
Walk the list with prev=null and curr=head; at each node save next=curr.next, set curr.next=prev (flip the link), then advance prev=curr and curr=next. When curr hits null, prev is the new head. It runs in O(n) time and O(1) space.
💡 Save-flip-advance, three pointers: prev / curr / next.
Flashcard
What signals tell you to reach for the linked-list reversal pattern, and which problems use it?
tap to reveal →
Use it whenever a problem says 'reverse', 'flip direction', or asks you to rewire next pointers in place without allocating a new list. It is the engine behind Reverse Linked List, Reverse Linked List II, Reverse Nodes in k-Group, and palindrome checks.
💡 'Reverse / flip / rewire in place' = three-pointer reversal.
Flashcard
How does an array compare to a linked list for random access vs. insertion/deletion at a known end?
tap to reveal →
Arrays give O(1) random access by index but costly O(n) insertion/deletion due to shifting. Linked lists have O(n) sequential access (no direct indexing) but O(1) insertion/deletion if the head/tail is known. Arrays are contiguous in memory; linked lists are not.
💡 Array = fast index, slow shift; List = slow walk, fast splice.
Flashcard
What distinguishes singly, doubly, and circular linked lists?
tap to reveal →
A singly linked list has one next pointer per node (forward only, last node points to NULL). A doubly linked list adds a prev pointer for two-way traversal and easier deletion, at the cost of extra memory. A circular linked list has the last node point back to the first, forming a loop with no NULL terminator.
💡 Singly = one-way, Doubly = both-ways, Circular = loops back.
Flashcard
Why is a dummy (placeholder) head node useful, and which problems in this topic rely on it?
tap to reveal →
A dummy node placed before the real head removes the special case of modifying the original first node, so the same relinking logic works everywhere; you return dummy.next at the end. It is used in Merge Two Sorted Lists, Add Two Numbers, Swap Nodes in Pairs, and Reverse Nodes in k-Group.
💡 Dummy head = no first-node special case; return dummy.next.
Flashcard
In Add Two Numbers, why are digits stored in reverse order and how is the carry handled?
tap to reveal →
Digits are stored least-significant-first so you can add from the head outward, mimicking manual addition. At each step sum = d1 + d2 + carry; the new node value is sum % 10 and carry becomes sum // 10. After the loop, if carry is non-zero, append one more node with the carry.
💡 value = sum % 10, carry = sum // 10; don't forget the trailing carry.
Flashcard
How does the Odd Even Linked List rearrangement work in O(1) space?
tap to reveal →
Keep an odd pointer at the head and an even pointer at the second node, saving even_head. Repeatedly set odd.next = odd.next.next and even.next = even.next.next, advancing each; finally link the last odd node to even_head. Indices are 1-based, so odd-INDEXED nodes come first.
💡 Weave two chains, then stitch last-odd to even_head.
Q1. While reversing a singly linked list with prev/curr, what must you do BEFORE executing curr.next = prev?
Q2. For the input list [3, 5, 2], what does the reverse-linked-list algorithm return?
Q3. Which statement about random access best contrasts arrays and linked lists?
Q4. In Merge Two Sorted Lists, how is the head of the merged result obtained?
Q5. In Reverse Nodes in k-Group, what happens to a final group that has fewer than k nodes?
Q6. Which advantage is UNIQUE to a doubly linked list over a singly linked list?