LC206 Reverse Linked List 🟢

This matches the "reverse the chain" signal — and the mantra: "Before you flip a link, make sure you haven’t stranded the rest of the train!"

1. Mindset Shift

The naive way is to copy every value into a list, reverse it, and build a new linked list — correct, but Space O(n).

Key insight: don’t move the cargo — just walk and flip each next pointer to point backward in place, using prev and cur.

Picture crossing a bridge and folding the planks behind you — you must know where the next step lands before you fold!

2. The Logic — 4 Steps

Open prev/cur, then flip one node at a time:

1. Prep pointers — prev = None · cur = head
2. Save the path — nxt = cur.next (don’t lose the train!)
3. Flip the link — cur.next = prev, then advance prev to cur · cur to nxt
4. Done — when cur is None, prev is the new head → return prev

3. LeetCode-Ready Code

Memorize the four lines in the loop — this move shows up in many problems:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        prev = None                 # behind cur (nothing yet)
        cur = head                  # node under consideration

        while cur:
            nxt = cur.next          # 1) save next (don’t lose the train)
            cur.next = prev         # 2) flip the link backward
            prev = cur              # 3) advance prev
            cur = nxt               # 4) advance cur to the saved node

        return prev                 # after the loop, prev is the new head

4. Dry Run — 1 → 2 → 3

The | mark splits two pieces: left = already flipped · right = not touched yet — final train [3, 2, 1]

5. Edge Cases & Pitfalls

The "forgot to save nxt first" case — classic trap:

• The moment you set cur.next = prev, the old forward link is gone
• You can’t walk onward — always do nxt = cur.next first

6. Time & Space Complexity

• Time O(n) — one pass through every node
• Space O(1) — a few pointers, no new list