Reverse Linked List

Reversing a linked list is the single most important routine in this section. It is asked on its own, and it is a building block inside Reorder List, Palindrome Linked List and Reverse Nodes in k-Group. If you can write it from memory without thinking about the order of lines, the harder problems get much easier.

The difficulty is not the idea — "make every arrow point the other way" — but the rule from the core lesson: you cannot go back. The moment you flip a node's next pointer, you lose your only route to the rest of the list, unless you saved it first.

The problem

You are given the head of a singly linked list. Reverse the list and return the new head. Use the ListNode class from the core lesson.

• 1 → 2 → 3 → 4 → 5 → 5 → 4 → 3 → 2 → 1.
• 1 → 2 → 2 → 1.
• An empty list → an empty list.

Constraints: 0 to 5,000 nodes. Reverse the nodes themselves, using O(1) extra space.

Clarifying questions

• Should I reverse the nodes, or is building a new list fine? Reverse the existing nodes in place.
• Can I change the values instead of the links? No. In real code a node often carries a large payload; swapping values is a different, weaker answer.
• Empty list? Return None.
• Is there possibly a cycle? Assume not.

Approach 1: copy the values out, build a new list

Read the values into a Python list, then build a new linked list from the last value to the first.

1def reverse_list_copy(head: ListNode | None) -> ListNode | None:2    """Read the values into a list, then build a new list backwards. O(n) space."""3    values = []4    while head is not None:5        values.append(head.value)6        head = head.next7    dummy = ListNode()8    tail = dummy9    for value in reversed(values):10        tail.next = ListNode(value)11        tail = tail.next12    return dummy.next

Time: O(n). Space: O(n) — an array of n values and n new nodes.

Unlike most brute forces in this course, this is not slow; its time is already optimal. It fails the problem in a different way. It uses O(n) extra memory, it creates new nodes instead of reversing the given ones, and any other code holding a reference to the old nodes still sees them in the old order. It is a fine sentence to say first ("the easy way copies, but you want it in place"), not a solution to submit.

The key insight

Walk the list once and flip each node's pointer as you pass it. At every moment the list is split into two separate pieces:

• a reversed part, whose head is previous — the nodes already flipped, now pointing backwards;
• an untouched part, whose head is current — the nodes still in original order.

Each step moves one node from the front of the untouched part to the front of the reversed part. When the untouched part is empty, previous is the head of the whole reversed list. That is the invariant, and it tells you what to return.

The step itself needs a third pointer. To move current over, you set current.next = previous. But current.next was the only reference to the rest of the untouched part. So first save it in next_node. Save, flip, then advance both previous and current. The order of those four lines is not a style choice; any other order loses nodes or picks up the wrong one.

Approach 2: three pointers, in place

1def reverse_list(head: ListNode | None) -> ListNode | None:2    """Flip every next pointer in one pass. O(n) time, O(1) space."""3    previous = None                # head of the reversed part4    current = head                 # first node not yet flipped5    while current is not None:6        next_node = current.next   # 1. save the rest7        current.next = previous    # 2. flip8        previous = current         # 3. grow the reversed part9        current = next_node        # 4. step into the saved rest10    return previous

Line 1 must come before line 2, or the rest of the list is unreachable. Line 3 must come before line 4, or previous would take the value of the wrong node. The loop ends when current is None; at that point previous holds the old last node, which is the new head.

Dry run on 1 → 2 → 3:

After step 3 current is None, so the loop stops and the function returns node 3. Each row moves exactly one node across, and the two parts never point into each other.

Time: O(n) — one pass, four assignments per node. Space: O(1) — three variables, whatever the length.

Approach 3: recursion

1def reverse_list_recursive(head: ListNode | None) -> ListNode | None:2    """Reverse the tail, then hook head onto its end. O(n) stack space."""3    if head is None or head.next is None:4        return head                # empty or one node: already reversed5    new_head = reverse_list_recursive(head.next)6    head.next.next = head          # the old second node points back at head7    head.next = None               # head is the new tail8    return new_head

Trust the recursive call to reverse everything after head. When it returns, head.next still points at the node that used to follow head — which is now the tail of the reversed remainder. head.next.next = head hangs head after that tail. Then head.next = None makes head the end of the list. new_head (the old last node) is passed up unchanged through every level.

Time: O(n). Space: O(n) — one stack frame per node. We ran it on a 5,000-node list and CPython raised RecursionError, because its default limit is about 1,000 frames. So it does not meet an O(1)-space requirement, and it is unsafe on long lists. Offer it as an alternative, and say this before the interviewer does.

Edge cases

• Empty list: the loop never runs; previous is None, which is returned.
• One node: one iteration sets its next to None (it already was) and returns it.
• Two nodes: the smallest case where a pointer truly flips. Trace it: after step 1 you have 1 → None and current = 2; after step 2, 2 → 1 → None.
• Recursive version without head.next = None: the first two nodes point at each other, forming a cycle. Printing the list then never ends.

Follow-ups

• Reverse only positions left to right (Reverse Linked List II): walk a dummy-based pointer to the node before left, reverse exactly right − left + 1 nodes with the same loop, then reconnect both ends. Still one pass, O(1) space.
• Is the list a palindrome? Find the middle (see Fast and Slow Pointers), reverse the second half, compare the halves node by node, and reverse it back to restore the input.
• Reverse in groups of k: the same loop applied to each group, with care at the joins. It is the last lesson in this section.