Reverse Linked List

Difficulty: Easy

Problem

Given the head of a singly linked list, reverse the list, and return the reversed list. Each node has a 'val' property and a 'next' pointer to the next node (or null for the last node).

Example

Input: head = [1, 2, 3, 4, 5]
Output: [5, 4, 3, 2, 1]
Explanation: The linked list 1 → 2 → 3 → 4 → 5 becomes 5 → 4 → 3 → 2 → 1 after reversal.

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)