1.5 Linked Lists — DSA Crash Course

Deep Dive: Pointer Manipulation Visualized

Beginner tip: A linked list is like a chain of paper clips. Each clip (node) holds a value and a pointer to the next clip. You cannot jump to clip #5 directly -- you must follow the chain from clip #1. The advantage: inserting or removing a clip in the middle is instant (just re-link), unlike arrays where you must shift everything.

Reversing a Linked List -- The 3-Pointer Dance

Initial:  None <- prev    curr -> 1 -> 2 -> 3 -> 4 -> None

Step 1:   Save next = curr.next (2)
          Point curr.next = prev (None)
          Advance: prev = curr (1), curr = next (2)
          Result:  None <- 1    2 -> 3 -> 4 -> None
                        prev  curr

Step 2:   Save next = 3
          Point 2.next = 1
          Advance: prev=2, curr=3
          Result:  None <- 1 <- 2    3 -> 4 -> None

Step 3:   None <- 1 <- 2 <- 3    4 -> None
Step 4:   None <- 1 <- 2 <- 3 <- 4    curr=None, prev=4 (new head!)

Why 3 pointers: You need next because once you point curr.next backward, you lose the forward link. Save it first.

Boxes-and-Arrows: prev / curr / next at Each Step

For list 1 -> 2 -> 3 -> None, here is the state of all three pointers BEFORE, DURING, and AFTER the very first iteration of the reversal loop.

BEFORE (just entered the loop body):

   prev      curr        nxt = ?
    |         |
    v         v
  None      [ 1 ] -> [ 2 ] -> [ 3 ] -> None

DURING -- step 1 of 3: save next FIRST
                              nxt
                               |
                               v
  None      [ 1 ] -> [ 2 ] -> [ 3 ] -> None
   ^         ^
   |         |
  prev      curr

DURING -- step 2 of 3: flip curr.next to point at prev
                              nxt
                               |
                               v
  None  <- [ 1 ]    [ 2 ] -> [ 3 ] -> None
   ^         ^        ^
   |         |        |
  prev?    curr      ...still the rest of the list,
                     reachable ONLY through nxt.

DURING -- step 3 of 3: advance prev and curr
            prev     curr      nxt no longer needed
              |       |
              v       v
  None  <- [ 1 ]    [ 2 ] -> [ 3 ] -> None

AFTER iteration 1 (ready for iteration 2):
              prev     curr
                |       |
                v       v
  None  <- [ 1 ]      [ 2 ] -> [ 3 ] -> None

After two more iterations the picture finishes as None <- 1 <- 2 <- 3 with prev = 3 (new head) and curr = None (loop exits).

Where the "I almost lost the rest of the list" bug lives: the order of the three reassignments is not optional.

# WRONG -- you just orphaned 2 and 3
curr.next = prev      # 1.next = None ... 2 and 3 are now unreachable
nxt = curr.next       # nxt = None  (oops)
prev = curr; curr = nxt

# RIGHT -- save the forward link FIRST
nxt = curr.next       # remember 2 before we overwrite the pointer
curr.next = prev      # safe to flip now
prev = curr; curr = nxt

The mantra: save next, flip curr.next, then advance prev and curr. In that order, every time.

Fast/Slow Pointers -- Why They Meet

For cycle detection, slow moves 1 step, fast moves 2 steps:

If there IS a cycle of length C:
  Once both are in the cycle, the gap shrinks by 1 each step.
  They MUST meet within C steps.

If there is NO cycle:
  Fast hits None first. Done.

For finding the middle: when fast reaches end, slow is at middle (fast travels 2x distance).

Quick Reference (Cheat Sheet)

Before You Start -- How to Think About Linked Lists

Why They Exist

Need: Dynamic size + O(1) insert/delete at a known position. Trade-off: You lose O(1) random access (no arr[i]). You must traverse.

The Linked List Mindset

In linked list problems, you're manipulating pointers, not values. Draw arrows on paper.

Always draw the before/after state on paper. Pointer manipulation is error-prone when you do it in your head.

Three Techniques That Solve 90% of LL Problems

1. Dummy Node

dummy = ListNode(0)
dummy.next = head
# ... do work ...
return dummy.next

Eliminates edge cases where the head changes (deletions, insertions at front).

2. Fast & Slow Pointers

Slow moves 1 step, Fast moves 2 steps.
- Find middle: when fast reaches end, slow is at middle
- Detect cycle: if fast == slow, there's a cycle
- Find cycle start: reset one pointer to head, move both 1 step

3. Reverse in Place

prev = None, curr = head
while curr:
    nxt = curr.next
    curr.next = prev
    prev = curr
    curr = nxt
return prev  # new head

Memorize this. It appears in 50% of LL problems.

When You See a Linked List Problem, Ask Yourself

1. Would a DUMMY NODE simplify edge cases? -> Almost always yes
2. Do I need to find MIDDLE or detect CYCLE? -> Fast & Slow
3. Do I need to REVERSE all or part? -> Iterative reverse template
4. Am I MERGING two lists? -> Two-pointer merge (like merge sort)
5. Is this really just an ARRAY problem in disguise? -> Sometimes convert to array, solve, convert back

Common Mistakes

Losing reference to head or next during pointer manipulation
Not handling None (end of list) -- always check node is not None before node.next
Forgetting to return dummy.next instead of head when head might change

Problems

#	Problem	Difficulty	Pattern	Status
1	Reverse Linked List	Easy	Iterative / Recursive	[ ]
2	Detect Cycle (Floyd's)	Easy	Fast & Slow	[ ]
3	Merge Two Sorted Lists	Easy	Two Pointer merge	[ ]
4	Remove Nth Node From End	Medium	Two Pointer gap	[ ]
5	Reorder List	Medium	Mid + Reverse + Merge	[ ]
6	LRU Cache	Hard	HashMap + DLL	[ ]