DSA With AI
Week 3 ยท Linked List

Reverse Linked List

Reverse a singly linked list. The browser runner uses a list of values, but the interview version is about redirecting ListNode next pointers.

Easy Linked List Week 3 Practice runner

Frame the problem

  • Save the next node before overwriting curr.next.
  • Empty and single-node lists must work.
  • The pointer version should use O(1) extra space.
1. Reveal example inputs and outputs

Example 1

Input:

reverse_list([
  1,
  2,
  3,
  4,
  5
])

Output:

[
  5,
  4,
  3,
  2,
  1
]

Example 2

Input:

reverse_list([
  1
])

Output:

[
  1
]
2. Brute force first

How would a stack solve this? Why is pointer reversal the stronger linked-list answer?

3. Reveal the insight ladder
  1. Keep prev as the reversed prefix.
  2. Keep curr as the node being processed.
  3. Store next_node, redirect curr.next to prev, then advance.
  4. Return prev after curr falls off the list.
4. Dry run before code
  1. 1 -> 2 -> 3.
  2. After 1: 1 -> None.
  3. After 2: 2 -> 1 -> None.
  4. After 3: 3 -> 2 -> 1 -> None.
5. Reveal final Python solution 
def reverse_list(values):
    return values[::-1]

Complexity: Pointer version: time O(n), space O(1). Browser value-list version returns a new O(n) list.

Interview narration

  • The key is not losing the rest of the list when overwriting next.
  • prev is the head of the reversed part.
  • curr walks the original remainder.

Common traps

  • Overwriting curr.next before saving next_node.
  • Returning curr instead of prev.
  • Forgetting the empty list.

Follow-up drills

1. What is the real ListNode loop?

while curr: next_node = curr.next; curr.next = prev; prev = curr; curr = next_node. Return prev.

2. How would recursion work?

Reverse the tail, then point head.next.next back to head and set head.next to None. It uses O(n) call stack.

Interactive runner

Write the required Python function. Your code runs locally in this browser. Hints reveal one failing case at a time.