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

Traverse the list, store all values in an array, then create a new reversed linked list from the array.

Steps

  1. Traverse list, store all values in an array
  2. Reverse the array
  3. Walk the list again, overwriting values from reversed array
  4. Return the head

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

Trade-offs

  • Uses O(n) extra space for the array
  • Requires two passes through the list
  • 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, current = head
  2. Save current.next in nextTemp
  3. Point current.next to prev (reverse the link)
  4. Move prev = current, current = nextTemp
  5. Repeat until current is null, then return prev

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

Pseudocode

function reverseList(head):
    prev = null
    current = head
    
    while current is not null:
        nextTemp = current.next
        current.next = prev
        prev = current
        current = nextTemp
    
    return prev

Hints

  • You need to change each node's 'next' pointer to point to the previous node instead
  • Keep track of three pointers: previous, current, and next
  • Before changing current.next, save the next node so you don't lose the rest of the list

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, current, nextTemp) 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