Reverse Linked List

Difficulty: Easy

Problem

You are given the head of a singly linked list. Flip the direction of the links so the list runs backwards, and return the new head. Each node has a 'val' property and a 'next' pointer to the following node (or null for the last node).

Example

Input: head = [3, 6, 9, 12]
Output: [12, 9, 6, 3]
Explanation: The list 3 → 6 → 9 → 12 becomes 12 → 9 → 6 → 3 once every link points the other way.

Brute-force approach

Walk the list and copy every value into an array. Reverse the array. Then walk the list again and write the reversed values back into the same nodes. For 4 nodes that is 4 visits to read plus 4 to write, 8 visits in all, and 4 extra numbers in the array.

Steps

  1. Traverse list, store all values in an array
  2. Reverse the array
  3. Walk the list again, writing the reversed values back into the same nodes
  4. Return the head

Time complexity: O(n) · Space complexity: O(n)

Trade-offs

  • Uses O(n) extra space for the array: n extra numbers
  • Requires two passes through the list: n visits to read plus n to write, so 2n visits (8 for 4 nodes)
  • Modifies values instead of actually reversing pointers

Optimal approach

Key insight: At each step, save the next node, reverse the current pointer, then advance all three pointers forward.

Reverse the linked list in-place by iteratively changing each node's next pointer to point to the previous node.

Steps

  1. Initialize prev = null, curr = head
  2. Save curr.next in nxt
  3. Point curr.next to prev (reverse the link)
  4. Move prev = curr, curr = nxt
  5. Repeat until curr is null, then return prev

Time complexity: O(n) · Space complexity: O(1)

Pseudocode

function reverseList(head):
    prev = null
    curr = head
    
    while curr is not null:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    
    return prev

Hints

  • You need to change each node's 'next' pointer to point to the previous node instead
  • Keep track of three names: prev (the node behind), curr (the node whose arrow flips now), and nxt (a saved copy of curr.next)
  • Each round goes in this order: save nxt = curr.next, flip curr.next to prev, then step prev and curr forward
  • The saved nxt is the only way to the rest of the list once curr.next changes, so save it before you flip
  • The first node has nothing behind it, so its new arrow points to None (null). That is why prev starts as null

Complexity questions

What is the time complexity of the brute force approach (store values, reverse array, overwrite)?

O(n). We traverse the list twice (once to collect, once to overwrite) and reverse the array once. All are O(n), so total is O(n).

What is the space complexity of the brute force approach?

O(n). We store all n values in an array, requiring O(n) extra space.

What is the time complexity of the iterative three-pointer approach?

O(n). We traverse the list once, doing O(1) work per node. Total: O(n).

What is the space complexity of the iterative three-pointer approach?

O(1). We only use three pointers (prev, curr, nxt) regardless of list size. That's O(1) extra space.

Check your understanding of Reverse Linked List

What does it mean to reverse a linked list?

Reverse the direction of all the 'next' pointers so the last node becomes the head. Reversing a linked list means changing the direction of every 'next' pointer. The original tail becomes the new head, and the original head becomes the new tail pointing to null.

Given the list 1 → 2 → 3 → null, what should node 2's 'next' pointer point to after reversal?

Node 1. After reversal the list becomes 3 → 2 → 1 → null. So node 2's 'next' pointer now points to node 1 instead of node 3.

In the reversed list 5 → 4 → 3 → 2 → 1 → null, what is the head and what is the tail?

Head = node(5), Tail = node(1). After reversal, the original tail node(5) becomes the new head, and the original head node(1) becomes the new tail pointing to null.

Related problems

Keep practising