{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Reverse Linked List – Solution & Complexity

Interview solutions
/
Reverse Linked List

Watch: Reverse a Linked List with three pointers

Walk the list with prev, curr and next. At each node save next first, point curr back at prev, then move both pointers forward. When curr is None, prev is the new head: O(n) time, O(1) space. The recursive version works too but uses O(n) stack.

Solution Walkthrough

  1. Step 1: Understand the Goal

    • The input is a chain of nodes: 1 -> 2 -> 3 -> null.
    • Reversing it means every next pointer should point the other way: 3 -> 2 -> 1 -> null.
    • The new head is the old tail, so the function must return the node that used to be last.

  2. Step 2: Track Three Pointers

    • Walking the list forward while rewriting next pointers destroys the way back unless you keep a reference to what came before.
    • Keep three pointers as you walk: prev (already-reversed portion), curr (node being processed), and next_node (saved before you overwrite curr.next).
    • Start with prev = None since the new tail's next must be null.
    def reverse_list(head):
    prev = None
    curr = head
    return prev

  3. Step 3: Rewire One Node at a Time

    • Save curr.next before overwriting it, so you don't lose the rest of the list.
    • Point curr.next backward at prev.
    • Advance both prev and curr one step forward for the next iteration.
    def reverse_list(head):
    prev = None
    curr = head
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    return prev

  4. Step 4: Confirm the Loop Termination and Complexity

    • The loop stops when curr becomes None, meaning every original node has been rewired.
    • At that point prev holds the new head (the old tail), which is exactly what the function returns.
    • Each node is visited once, so time complexity is O(n); only three pointers are kept, so space complexity is O(1).
    class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def reverse_list(head: ListNode) -> ListNode:
    prev = None
    curr = head
    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node
    return prev

  5. Step 5: Alternative: Recursive Reversal

    • Recursively reverse everything after the head first, then fix up the one link at the current level.
    • Base case: an empty list or single node is already reversed.
    • After the recursive call, head.next is the new tail, so set head.next.next = head and detach head.next to avoid a two-node cycle.
    • This trades the O(1) space of the iterative version for O(n) call-stack space.
    def reverse_list(head: ListNode) -> ListNode:
    if head is None or head.next is None:
        return head
    new_head = reverse_list(head.next)
    head.next.next = head
    head.next = None
    return new_head

FAQ

See also

Practice Reverse Linked List online (run code in the browser)Swap Nodes in Pairs solution (medium)Flatten Binary Tree to Linked List solution (medium)Merge Two Sorted Lists solution (easy)Reverse Linked List II solution (medium)All coding interview problems