Blog

Reverse Linked List

Candidates have reported being asked to reverse a linked list at Amazon, Microsoft, and ByteDance. We'll work with a singly linked list, where each node has a next reference. We need to reverse those references in place and return the new head while keeping the existing nodes and values.

In a doubly linked list, we would swap each node's next and previous references and update the head.

Input headnull81422Returned headnull81422

Before changing a link, we need to keep a reference to the next node so that we can continue through the list afterward.

Save the next node first

We use three pointers. We keep the head of the reversed portion in prev, the node we're processing in current, and its original next node in following before we change the link.

Start with prev = None and current = head. Save current.next in following, then point current.next at prev.

After processing node 8
nullnullprev8current14following22nullnullprev8current14following22

After reversing the link at node 14, move prev to 14 and current to the saved node 22. Repeat the same save, reverse, and advance sequence until current is null, then return prev as the new head.

Python
def reverse_list(head):
    prev = None
    current = head
    while current is not None:
        following = current.next
        current.next = prev
        prev = current
        current = following
    return prev

Retain the returned head in the caller with head = reverse_list(head). We visit each of the n nodes once, taking O(n) time and O(1) extra space. With a conventional recursive reversal, we use O(n) call-stack space, so we use iteration for the constant-space requirement.