CodingwithDom
Subscribe

Reverse a linked list

Interview Prep 2 min read
Short answer

Walk the list keeping prev, curr and next. On each step, point curr.next backwards at prev, then advance all three. Return prev.

python
def reverse_list(head):
    prev = None
    curr = head

    while curr:
        next_node = curr.next    # save it before we overwrite
        curr.next = prev         # reverse the pointer
        prev = curr              # advance prev
        curr = next_node         # advance curr

    return prev                  # prev is the new head

O(n) time, O(1) space.

#The order matters

Saving next_node first is essential. The moment you write curr.next = prev, the rest of the list is unreachable from curr. Overwrite that pointer before saving it and you have lost everything after this node.

#Trace it

text
1 → 2 → 3 → None

prev=None  curr=1     1 → None,  prev=1  curr=2
prev=1     curr=2     2 → 1,     prev=2  curr=3
prev=2     curr=3     3 → 2,     prev=3  curr=None
loop ends, return prev = 3

3 → 2 → 1 → None

#Why return prev and not curr

When the loop ends, curr is None — it walked off the end. prev is sitting on the last node processed, which is the new head.

#The recursive version

python
def reverse_list(head):
    if not head or not head.next:
        return head
    new_head = reverse_list(head.next)
    head.next.next = head
    head.next = None
    return new_head

Elegant, but O(n) stack space and it blows up on a long list. Mention it, then use the iterative one.

#Drawing beats thinking

In an interview, draw the three boxes and the arrows before writing code. Pointer problems are where silent coding goes wrong fastest, and the interviewer wants to see the reasoning anyway.

Related answers