DSA sheet · Linked List · Reversal pattern

Reverse a Linked List

This video opens the third linked-list pattern: reversal. The question is the simplest member of the family: turn the whole list around so the old tail becomes the new head. The teacher first solves it the "array way" (copy the values out, write them back in reverse), then shows the real trick: walk once with three pointers, prev, curr and nxt, and flip one arrow per step. These four lines of code come back in almost every later problem of this pattern (palindrome list, twin sum, reverse between, k-group, reorder list…), so it's worth learning them until you can write them half asleep. At the end we also do the recursive version with the call stack, because interviewers often ask for both.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

Part 0 · Linked lists from scratch (and what "reversing" means)
Part A · Brute force: copy values into a list, write them back reversed
Part B · Optimal: one pass with prev / curr / nxt
Part C · The recursive version (with the call stack)
Part D · Revision page

Part 0 · Linked lists from scratch

What is a node?

A linked list is a chain of small boxes called nodes. Each node holds two things: a value (val) and a link (next) to the node after it. The last node's next is None, which means "the chain ends here".

given by LeetCode, don't write this in the solution

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val      # the number stored in this box
        self.next = next    # the next box, or None at the end

[1] → [4] → [3] → [5] → [2] → None
head                          (tail = the last real node, [2])

head: the first node. The problem only gives you this one pointer. Every other node is reached by following arrows from it.
tail: the last real node, the one whose next is None.
An empty list is just head = None.

Walking a list

To visit every node we keep a moving pointer, usually called curr (current), and step with curr = curr.next until it falls off the end:

the basic walk

curr = head               # start at the first box (head itself never moves)
while curr:               # same as: while curr is not None
    print(curr.val)
    curr = curr.next      # follow the arrow one step

We copy head into curr (the teacher calls this "making an alias of head") so that head still points at the start when the walk is over.

No index access

In an array you can jump straight to arr[3]. A linked list has no indexes: the nodes are scattered in memory and the only way to reach the 4th node is to start at head and follow 3 arrows. So reaching position i costs O(i), and reaching the end costs O(n). Worse, the arrows go only forward. From a node you can't step back to the one before it. Remember that, it's the whole reason this problem is interesting.

Why you must save `next` before changing a pointer

The next field of a node is the only road to the rest of the list. If you overwrite it, the rest of the chain is gone (nothing else points to it):

before:  [1] → [4] → [3] → None
do:      one.next = None           (without saving [4] first)
after:   [1] → None      [4] → [3] → None   ← nobody points here any more: lost!

So the rule for every pointer-changing problem is: store curr.next in a variable first, then change curr.next. In Python we call that variable nxt, because next is already a built-in function name.

What does "reverse a linked list" mean?

Reversing doesn't mean moving boxes around. It means turning every arrow the other way. The boxes stay where they are. Once every arrow is flipped, the old tail is the node you start reading from, so it's the new head we must return, and the old head points to None.

before:  [1] → [4] → [3] → [5] → [2] → None
after:   None ← [1] ← [4] ← [3] ← [5] ← [2]
read from the new head:  [2] → [5] → [3] → [4] → [1] → None

The linked-list patterns so far

The teacher lists the patterns of this sheet: basic operations (insert, delete, search), fast & slow pointers (middle, cycles), reversal (this video) and merge & sort. The name of this question already says which one to use, but she still starts from a simpler brute force so we see why reversal is better.

Her general rule for linked-list questions: an O(n²) solution is rare. The brute force is usually "two or three passes" (O(2n), O(3n)) or "use an extra list" (O(n) space). The optimal is usually one pass (O(n), sometimes O(n/2)) with no extra space.

Part A · Brute force: copy values out, write them back reversed

LeetCode 206

1The question in simple words

You get the head of a singly linked list (each node points only forward). Reverse the list and return the new head.

input:   [1] → [4] → [3] → [5] → [2] → None
output:  [2] → [5] → [3] → [4] → [1] → None

After reversing, the old head [1] becomes the tail (it must point to None), and the old tail [2] becomes the head. We return [2], so whoever reads from it sees the values in reverse order. (This is the list the teacher draws. LeetCode's own example is 1 → 2 → 3 → 4 → 5.)

Small cases: an empty list stays empty (return None). A one-node list is already reversed.

2What the constraints tell us

Number of nodes: 0 to 5000 → 0 is allowed, so head can be None. Our code must return None for it without crashing.
Values: −5000 to 5000 → small numbers, nothing special.
5000 is small (the teacher calls it "around 10³"). Even an O(n²) solution is only 25 million steps, well under the ~10⁸ limit for TLE. So speed is not the problem here; the point is to learn the clean O(n) / O(1) reversal, because it's the building block for harder questions.

3Intuition: what if it were an array?

The teacher's habit: forget the linked list for a moment and ask how you'd do it on an array [1, 4, 3, 5, 2].

On an array you'd use two pointers: left at the first index, right at the last. Swap them, move left forward and right backward, and repeat until they meet.

[1, 4, 3, 5, 2]    L=0, R=4 → swap → [2, 4, 3, 5, 1]
[2, 4, 3, 5, 1]    L=1, R=3 → swap → [2, 5, 3, 4, 1]
[2, 5, 3, 4, 1]    L=2, R=2 → same index, swapping is pointless → stop

The middle 3 stays where it is. The array is reversed.

4Building the logic: why two pointers fail on a list, and the fix

Doubt 1: why can't we do the same two-pointer swap on the linked list?
→ left can move forward with left = left.next, fine. But right has to move backward, and a singly linked list has no backward arrow. right.next goes further right, not left. To walk backward you'd first have to reverse (half of) the list, and reversing is exactly what we don't know how to do yet. So this idea is stuck.

Second idea: the trouble is that we can't read the list backward. But a Python list can be read backward. So:

Walk the linked list once and copy every value into an extra list: vals = [1, 4, 3, 5, 2].
Walk the linked list again from head, and overwrite each node's value with the values of vals read from the end: first node gets 2, second gets 5, then 3, 4, 1.

The arrows never change, only the numbers inside the boxes. Since head still points to the first box (which now holds 2), we return head itself.

Doubt 2: is changing the values (instead of the links) really "reversing the list"?
→ For LeetCode it passes, because the judge only reads the values from the returned head. In an interview, though, you'll often hear "don't change the values, change the links", and real nodes may carry much more data than one number. That's one more reason to learn Part B. (This remark is mine, not from the video.)

5Approach steps

Make an empty list vals and a walker curr = head.
While curr is not None: append curr.val to vals, move curr = curr.next.
Put curr back at head.
Loop i from the last index of vals down to 0: set curr.val = vals[i], move curr = curr.next.
Return head (it never moved).

6Code (Python)

Brute force: extra list, two passes

class Solution:
    def reverseList(self, head):
        vals = []
        curr = head                      # alias, so head stays at the start
        while curr:                      # pass 1: copy the values out
            vals.append(curr.val)
            curr = curr.next

        curr = head                      # pass 2: start again from the front
        for i in range(len(vals) - 1, -1, -1):   # read vals from the end
            curr.val = vals[i]           # overwrite this box's value
            curr = curr.next
        return head                      # same first box, new value inside

7Code line by line

line	what it means
vals = []	The extra storage. This is what makes the space O(n).
curr = head	A walking copy of head. We must not lose head, because we return it.
while curr: vals.append(curr.val) curr = curr.next	Visit every node once and remember its value. For an empty list the loop doesn't run.
curr = head	Restart the walk from the first node.
for i in range(len(vals) - 1, -1, -1):	`i` goes n−1, n−2, …, 0 (the stop value −1 is not included). So we read the stored values back to front.
curr.val = vals[i] curr = curr.next	`curr` goes front to back while `i` goes back to front, so the 1st node gets the last value, the 2nd node the second-last value, and so on. The loop runs exactly n times, so `curr` never steps past the last node and crashes.
return head	Head is still the first box. Its value is now the old last value.

8Dry run

List [1] → [4] → [3] → [5] → [2]. Pass 1 gives vals = [1, 4, 3, 5, 2]. Pass 2:

step	curr is on (old value)	i	vals[i]	list after this step
1	1st box (1)	4	2	[2] → [4] → [3] → [5] → [2]
2	2nd box (4)	3	5	[2] → [5] → [3] → [5] → [2]
3	3rd box (3)	2	3	[2] → [5] → [3] → [5] → [2]
4	4th box (5)	1	4	[2] → [5] → [3] → [4] → [2]
5	5th box (2)	0	1	[2] → [5] → [3] → [4] → [1]

Notice we can safely overwrite: the old values are already saved in vals, so writing 2 into the first box doesn't lose the 1. Return head → 2 → 5 → 3 → 4 → 1 ✓

9Complexity & remember

Time O(2n) = O(n): one pass to copy the values, one pass to overwrite them.
Space O(n): the extra list vals holds all n values.

Remember the brute forceCopy values into a list → walk again from head → write them back from the end of the list. Two passes, O(n) extra space, the links never change.

Part B · Optimal: one pass with prev / curr / nxt

1The question (same as Part A), with a new goal

Same input and output. The goal now: one pass instead of two, and no extra list.

2What the constraints tell us

0 nodes is allowed → with head = None our loop must simply not run, and we must return None.
We're allowed to change the nodes in place, so we can rewire the arrows.

3Intuition: flip the arrows as you walk

The teacher's reasoning: if we want to finish in one pass and never come back, the only way is to change each node's next pointer while we're standing on it. Each node should point to the node before it instead of the one after it.

Picture walking along a row of signposts that all point right. As you reach each signpost, you turn it to point left, at the post you just left behind. When you reach the end, every sign points left, and the last post you touched is the new start.

To do this at a node we need to know three things, so we keep three pointers:

pointer	what it holds	why we need it
`prev`	the node just behind us (already flipped part)	this is where `curr.next` must point after the flip
`curr`	the node we're standing on	its arrow is the one we flip now
`nxt`	the node just ahead of us	after the flip, `curr.next` no longer leads forward. Without `nxt` we'd lose the rest of the list

4Building the four lines, the way the teacher does

Where does `prev` start? At None

Stand on the first node [1]. After reversal, [1] is the tail, so its arrow must point to None. So the very first "node behind us" is None. She literally draws a None box to the left of [1] and names it prev.

None   [1] → [4] → [3] → [5] → [2] → None
prev   curr

Startprev = None, curr = head

Line 1: save the road ahead

We want [1] to point to None instead of [4]. But [1].next is the only link to [4] → [3] → [5] → [2]. If we flip it now, that whole part is lost. So first save it:

Line 1nxt = curr.next

Line 2: flip the arrow

Now it's safe. What should curr.next become? Whatever prev holds. In round 1 that's None, which is exactly what the new tail needs.

Line 2curr.next = prev

Line 3: move `prev` forward

For the next node, "the node behind us" will be the node we're on now. So prev moves to curr.

Line 3prev = curr

Line 4: move `curr` forward, with `nxt`, NOT `curr.next`

Normally we'd write curr = curr.next. Here that's a trap.

Doubt 1: why curr = nxt and not curr = curr.next?
→ Line 2 already changed curr.next. It now points backward, to prev (None in round 1). So curr = curr.next would jump back to None (or to the previous node) instead of moving forward. The forward node is saved in nxt, so we use that.

Line 4curr = nxt

A neat memory trick: each line's left side is the previous line's right side

The teacher points out a "chain" in these four lines. After a line, the thing on its right side has been used up, so the next line fills it in:

nxt       = curr.next     ← curr.next was read, so next line refills it
curr.next = prev          ← prev was used, so next line refills it
prev      = curr          ← curr was used, so next line refills it
curr      = nxt           ← nxt was used, and line 1 refills it next round

So the order is fixed: nxt → curr.next → prev → curr, and it wraps around.

The loop condition: why `while curr`

These four lines handle one node, so they go inside a loop. But until when? She walks it through and tests each possible pointer:

Stop when nxt is None? Look at round 5: curr is on [2] and nxt is None, but [2]'s arrow has not been flipped yet. If we stopped there, [2] would never point to [5]. So the loop must not depend on nxt. We need one more round.
Loop while prev.next is not None? At the start prev is None, and None.next crashes (a null pointer error in Java, AttributeError in Python). Can't depend on prev either.
Loop while curr is not None. After round 5, curr moves to None, which means every node has been flipped. This is the right condition. It also handles the empty list: if head is None, the loop never runs.

What do we return? `prev`, not `head`

Doubt 2: why not return head like in Part A?
→ head still points to [1], and [1] is now the tail (it points to None). Returning head would give the list [1] → None, just one node. When the loop ends, curr is None and prev is on the last node we flipped, the old tail [2]. That's the new head. So return prev. (For an empty list, prev is still None, which is the right answer too.)

5Approach steps

Set prev = None, curr = head.
While curr is not None:
save the next node: nxt = curr.next
flip the arrow: curr.next = prev
step prev forward: prev = curr
step curr forward: curr = nxt
Return prev, the new head.

6Code (Python)

Reverse a linked list: iterative, O(n) time, O(1) space

class Solution:
    def reverseList(self, head):
        prev = None                 # the node behind us; the new tail must point here
        curr = head                 # the node we are flipping
        while curr:                 # until every node is flipped
            nxt = curr.next         # 1. save the road ahead
            curr.next = prev        # 2. flip the arrow backward
            prev = curr             # 3. step prev forward
            curr = nxt              # 4. step curr forward (NOT curr.next!)
        return prev                 # last node flipped = new head

7Code line by line

line	what it means
prev = None	The old head becomes the tail, and a tail points to None. So the first flip must point at None.
curr = head	Start on the first node.
while curr:	Run once per node. Stops when curr has walked past the old tail. Empty list → no rounds.
nxt = curr.next	Remember the rest of the list before we cut the arrow. In the last round this is None, and that's fine.
curr.next = prev	The actual reversal: this node now points back at the node before it.
prev = curr	The reversed part has grown by one node. prev marks its front.
curr = nxt	Move to the next unreversed node, using the saved pointer.
return prev	When curr is None, prev is on the old tail, the head of the reversed list.

Doubt 3: can I swap lines 3 and 4?
→ No. If you do curr = nxt first, then prev = curr copies the new curr, so prev and curr end up on the same node and the next flip makes a node point to itself. Always move prev first, then curr. (Python's one-liner curr.next, prev, curr = prev, curr, curr.next also works because the right side is evaluated before any assignment, but the four-line form is much easier to explain.)

8Dry run: every round, every pointer, every arrow

The teacher's list [1] → [4] → [3] → [5] → [2]. Each round has three snapshots: ① after saving nxt, ② after flipping curr.next (the red arrow is the one just rewired), ③ after moving prev and curr. The gap in a picture is where the list is "cut": everything left of it is already reversed, everything right of it still points forward.

Round 1 · curr is on [1]

① save:   nxt = curr.next      (nxt → [4])
None   [1] → [4] → [3] → [5] → [2] → None
prev   curr  nxt

② rewire: curr.next = prev     ([1].next: [4] → None)
None ← [1]   [4] → [3] → [5] → [2] → None
prev   curr  nxt

③ move:   prev = curr, curr = nxt
None ← [1]   [4] → [3] → [5] → [2] → None
       prev  curr

Round 2 · curr is on [4]

① save:   nxt = curr.next      (nxt → [3])
None ← [1]   [4] → [3] → [5] → [2] → None
       prev  curr  nxt

② rewire: curr.next = prev     ([4].next: [3] → [1])
None ← [1] ← [4]   [3] → [5] → [2] → None
       prev  curr  nxt

③ move:   prev = curr, curr = nxt
None ← [1] ← [4]   [3] → [5] → [2] → None
             prev  curr

Round 3 · curr is on [3]

① save:   nxt = curr.next      (nxt → [5])
None ← [1] ← [4]   [3] → [5] → [2] → None
             prev  curr  nxt

② rewire: curr.next = prev     ([3].next: [5] → [4])
None ← [1] ← [4] ← [3]   [5] → [2] → None
             prev  curr  nxt

③ move:   prev = curr, curr = nxt
None ← [1] ← [4] ← [3]   [5] → [2] → None
                   prev  curr

Round 4 · curr is on [5]

① save:   nxt = curr.next      (nxt → [2])
None ← [1] ← [4] ← [3]   [5] → [2] → None
                   prev  curr  nxt

② rewire: curr.next = prev     ([5].next: [2] → [3])
None ← [1] ← [4] ← [3] ← [5]   [2] → None
                   prev  curr  nxt

③ move:   prev = curr, curr = nxt
None ← [1] ← [4] ← [3] ← [5]   [2] → None
                         prev  curr

Round 5 · curr is on [2]

① save:   nxt = curr.next      (nxt → None)
None ← [1] ← [4] ← [3] ← [5]   [2] → None
                         prev  curr  nxt

② rewire: curr.next = prev     ([2].next: None → [5])
None ← [1] ← [4] ← [3] ← [5] ← [2]   None
                         prev  curr  nxt

③ move:   prev = curr, curr = nxt
None ← [1] ← [4] ← [3] ← [5] ← [2]   None
                               prev  curr

The same run as a hand table

round	pointers (at start of round)	which `.next` is rewired	the two pieces after the round	answer so far
1	prev=None · curr=[1] · nxt=[4]	[1].next: [4] → None	from prev: [1] → None from curr: [4] → [3] → [5] → [2] → None	keep going (curr is not None)
2	prev=[1] · curr=[4] · nxt=[3]	[4].next: [3] → [1]	from prev: [4] → [1] → None from curr: [3] → [5] → [2] → None	keep going (curr is not None)
3	prev=[4] · curr=[3] · nxt=[5]	[3].next: [5] → [4]	from prev: [3] → [4] → [1] → None from curr: [5] → [2] → None	keep going (curr is not None)
4	prev=[3] · curr=[5] · nxt=[2]	[5].next: [2] → [3]	from prev: [5] → [3] → [4] → [1] → None from curr: [2] → None	keep going (curr is not None)
5	prev=[5] · curr=[2] · nxt=None	[2].next: None → [5]	from prev: [2] → [5] → [3] → [4] → [1] → None from curr: None (nothing left)	curr is None → stop, return prev = [2]

After the loop

None ← [1] ← [4] ← [3] ← [5] ← [2]   None
                               prev  curr

return prev, and read the list from it:
[2] → [5] → [3] → [4] → [1] → None
returned head (prev)

head is still on [1], which now points to None. That's why returning head would give only [1]. ✓ The answer is 2 → 5 → 3 → 4 → 1.

Edge cases: empty list → loop never runs → return None. One node [7] → one round: nxt = None, [7].next = None (unchanged), prev = [7], curr = None → return [7].

9Complexity & remember

Time O(n): one pass, each node is flipped exactly once.
Space O(1): only three pointer variables, no matter how long the list is. (The teacher says "two variables"; with nxt it's three, still constant.)

Remember the four lines prev = None, curr = head
while curr: nxt = curr.next · curr.next = prev · prev = curr · curr = nxt
return prev
Loop on curr (not nxt, not prev). Move with nxt (not curr.next). Return prev (not head).

Part C · The recursive version

Not shown in this video. LeetCode's follow-up asks for both an iterative and a recursive solution, so it's added here for completeness.

1The question

Same as before: return the head of the reversed list. This time, no loop. A function that calls itself.

2What the constraints tell us

0 nodes allowed → the base case must handle head is None.
Up to 5000 nodes → the recursion goes one call deep per node, so up to 5000 calls wait at once. Python's default limit is about 1000, so a long list raises RecursionError unless you raise the limit (sys.setrecursionlimit(10**4)). This is a real reason to prefer the iterative version in Python.

3Intuition: trust the smaller problem

Recursion on a list means: a list is "one node + a smaller list". So handle the first node yourself and let a recursive call handle the rest.

Take [1] → [4] → [3] → [5] → [2]. Suppose a call on [4] → … already reversed the rest perfectly (the "leap of faith"):

[1] → [4] ← [3] ← [5] ← [2]        new_head = [2]
       ↓
      None

Now only [1] is left. Notice that [1].next still points to [4], and [4] is now the tail of the reversed part. So we just make [4] point back to [1], and make [1] point to None:

head.next.next = head      →   [4].next = [1]
head.next = None           →   [1].next = None
result:  [2] → [5] → [3] → [4] → [1] → None

4Building the logic

Base case: if the list is empty (head is None) or has one node (head.next is None), it's already reversed. Return head. That one node is the old tail, so it becomes the new head of the whole answer.
Recursive case: new_head = reverse(head.next). This reverses everything after head and gives back the new head (always the old tail, [2]).
Then fix the one arrow at our node: head.next.next = head, head.next = None.
Return new_head unchanged. Every level passes the same [2] up.

Doubt 1: why is head.next the tail of the reversed part?
→ Before the recursive call, head.next was the first node of the rest. Reversing the rest turns its first node into its last node. And the call never touched head itself, so head.next still points to that node. That's our free "pointer to the tail".

Doubt 2: what if I forget head.next = None?
→ After head.next.next = head, the two nodes point at each other ([1] ⇄ [4]), a cycle. Upper levels fix this for every node except the very first one, so the final list would end in a loop … → [4] → [1] → [4] → …. Setting head.next = None makes the old head a proper tail.

Doubt 3: why does the base case check head.next is None too, not only head is None?
→ With only head is None, the call on the last node [2] would recurse on None, get None back, and then head.next.next would mean None.next → crash. Stopping at the last node gives us the new head directly.

5Approach steps

If head is None or head.next is None → return head.
Reverse the rest: new_head = reverseList(head.next).
Make the node after head point back: head.next.next = head.
Cut head's forward arrow: head.next = None.
Return new_head.

6Code (Python)

Reverse a linked list: recursive, O(n) time, O(n) stack

class Solution:
    def reverseList(self, head):
        if head is None or head.next is None:   # 0 or 1 node: already reversed
            return head
        new_head = self.reverseList(head.next)  # leap of faith: reverse the rest
        head.next.next = head                   # the old next node points back at us
        head.next = None                        # we become the tail (for now)
        return new_head                         # the old tail, passed up unchanged

7Code line by line

line	what it means
if head is None or head.next is None: return head	Base case. Stops the recursion at the last node and handles the empty list.
new_head = self.reverseList(head.next)	Python pauses this call and reverses everything after head. On the way back it hands over the head of that reversed piece.
head.next.next = head	`head.next` is now the tail of the reversed piece. Point it back at head.
head.next = None	Remove the old forward arrow, so there's no 2-node cycle and head becomes the new tail.
return new_head	The answer's head is the same at every level: the old tail.

8Dry run with the call stack

Same list [1] → [4] → [3] → [5] → [2]. On the way down, nothing changes. Each call just waits for the call on the next node:

rev([1]): not a base case → calls rev([4]) and waits.
rev([4]) → calls rev([3]) and waits.
rev([3]) → calls rev([5]) and waits.
rev([5]) → calls rev([2]) and waits.
rev([2]): [2].next is None → base case → returns [2]. The stack is at its tallest here: 5 calls.

deepest point (step 5)

rev([1])rev([4])rev([3])rev([5])rev([2]) → [2]

Now the way back up. Each call fixes one arrow, then returns new_head = [2]:

back in rev([5]): head = [5], head.next = [2]. Set [2].next = [5], then [5].next = None.

[1] → [4] → [3] → [5] ← [2]       reversed piece: [2] → [5] → None
                   ↓
                  None

back in rev([3]): head = [3], head.next = [5] (still!). Set [5].next = [3], then [3].next = None.

[1] → [4] → [3] ← [5] ← [2]       reversed piece: [2] → [5] → [3] → None
             ↓
            None

back in rev([4]): head = [4], head.next = [3]. Set [3].next = [4], then [4].next = None.

[1] → [4] ← [3] ← [5] ← [2]       reversed piece: [2] → [5] → [3] → [4] → None
       ↓
      None

back in rev([1]): head = [1], head.next = [4]. Set [4].next = [1], then [1].next = None.

[1] ← [4] ← [3] ← [5] ← [2]       whole list: [2] → [5] → [3] → [4] → [1] → None
 ↓
None

rev([1]) returns [2]. The stack is empty. Final answer: 2 → 5 → 3 → 4 → 1 ✓

fixing [5] → [2]

rev([1])rev([4])rev([3])rev([5]) fixes [2]→[5]

fixing [3]

rev([1])rev([4])rev([3]) fixes [5]→[3]

fixing [4]

rev([1])rev([4]) fixes [3]→[4]

last fix

rev([1]) fixes [4]→[1]

Each waiting call remembers its own head. That's the "hidden storage" recursion gives us. The iterative version keeps the same information in prev instead.

9Complexity & remember

Time O(n): one call per node, constant work per call.
Space O(n): up to n calls wait on the call stack. That's worse than the iterative O(1), and in Python long lists hit the recursion limit.

Remember the recursive versionBase: 0 or 1 node → return head. Else new_head = rev(head.next); head.next.next = head; head.next = None; return new_head.

Part D · Revision page

	Brute force	Iterative (optimal)	Recursive
idea	copy values to a list, write them back from the end	walk once, flip each arrow to point at prev	reverse the rest, then hook head behind it
what changes	values only	links	links
passes	2	1	1 down + 1 back up
returns	`head`	`prev`	`new_head` (old tail)
empty list	loops don't run → None	loop doesn't run → prev = None	base case → None
time / space	O(2n) / O(n)	O(n) / O(1)	O(n) / O(n) stack

If you remember only 5 lines 1. Reversing = turning every arrow around; the old tail becomes the head.
2. Start with prev = None (the old head must end up pointing to None).
3. Order: nxt = curr.next → curr.next = prev → prev = curr → curr = nxt.
4. Loop while curr; stopping on nxt leaves the last node unflipped.
5. Return prev; head is now the tail.

Mistakes to avoid ✗ flipping curr.next before saving it (the rest of the list is lost)
✗ curr = curr.next after the flip (it walks backward)
✗ while nxt or while prev.next (misses the last node / crashes on None)
✗ returning head (you get a 1-node list)
✗ recursive version without head.next = None (cycle at the end)
✗ naming the variable next in Python (hides the built-in; use nxt)

test it yourself (paste under any of the solutions above)

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build(values):
    dummy = ListNode()
    tail = dummy
    for v in values:
        tail.next = ListNode(v)
        tail = tail.next
    return dummy.next

def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out

s = Solution()
print(to_list(s.reverseList(build([1, 4, 3, 5, 2]))))   # [2, 5, 3, 4, 1]
print(to_list(s.reverseList(build([1, 2]))))            # [2, 1]
print(to_list(s.reverseList(build([7]))))               # [7]
print(to_list(s.reverseList(build([]))))                # []

Based on this video: Reverse a Linked List | Reversal pattern

Reverse a Linked List

Part 0 · Linked lists from scratch

What is a node?

Walking a list

No index access

Why you must save next before changing a pointer

What does "reverse a linked list" mean?

The linked-list patterns so far

Part A · Brute force: copy values out, write them back reversed

1The question in simple words

2What the constraints tell us

3Intuition: what if it were an array?

4Building the logic: why two pointers fail on a list, and the fix

5Approach steps

6Code (Python)

7Code line by line

8Dry run

9Complexity & remember

Part B · Optimal: one pass with prev / curr / nxt

1The question (same as Part A), with a new goal

2What the constraints tell us

3Intuition: flip the arrows as you walk

4Building the four lines, the way the teacher does

Where does prev start? At None

Line 1: save the road ahead

Line 2: flip the arrow

Line 3: move prev forward

Line 4: move curr forward, with nxt, NOT curr.next

A neat memory trick: each line's left side is the previous line's right side

The loop condition: why while curr

What do we return? prev, not head

5Approach steps

6Code (Python)

7Code line by line

8Dry run: every round, every pointer, every arrow

The same run as a hand table

After the loop

9Complexity & remember

Part C · The recursive version

1The question

2What the constraints tell us

3Intuition: trust the smaller problem

4Building the logic

5Approach steps

6Code (Python)

7Code line by line

8Dry run with the call stack

9Complexity & remember

Part D · Revision page

Why you must save `next` before changing a pointer

Where does `prev` start? At None

Line 3: move `prev` forward

Line 4: move `curr` forward, with `nxt`, NOT `curr.next`

The loop condition: why `while curr`

What do we return? `prev`, not `head`