Reverse Linked List#

Problem#

Given the head of a singly linked list, reverse the list and return the new head. Each node points to the next; after reversal each node should point to what was previously in front of it.

Example#

Input 1 -> 2 -> 3 -> 4 -> 5 becomes 5 -> 4 -> 3 -> 2 -> 1. An empty list returns an empty list.

Optimal approach#

Walk the list once, rewiring each node’s next pointer to the node behind it. Keep three references: prev (the already-reversed portion, starting as None), curr (the node you are processing), and a temporary nxt so you do not lose the rest of the list when you overwrite curr.next. On each step, save nxt, point curr.next back at prev, then advance both prev and curr forward. When curr falls off the end, prev is the new head.

A recursive version exists but uses O(n) stack space; the iterative version runs in O(1) extra space and is what interviewers usually expect first.

Solution#

 1class ListNode:
 2    def __init__(self, val=0, next=None):
 3        self.val = val
 4        self.next = next
 5
 6
 7def reverse_list(head: ListNode | None) -> ListNode | None:
 8    prev = None
 9    curr = head
10    while curr:
11        nxt = curr.next
12        curr.next = prev
13        prev = curr
14        curr = nxt
15    return prev
16
17
18def build(values):
19    head = None
20    for value in reversed(values):
21        head = ListNode(value, head)
22    return head
23
24
25def to_list(node):
26    out = []
27    while node:
28        out.append(node.val)
29        node = node.next
30    return out
31
32
33print(to_list(reverse_list(build([1, 2, 3, 4, 5]))))  # [5, 4, 3, 2, 1]

Complexity#

• Time: O(n), one pass.
• Space: O(1), only three pointers.

See the linked lists topic for more pointer drills, then continue the 60-day challenge.