Reverse Linked List

easy
Linked ListLinked ListRecursion

Given the head of a singly linked list, reverse the list and return the reversed list. Each node in the list contains an integer value and a pointer to the next node.

Examples

Example 1

  • Input: head = [1,2,3,4,5]
  • Output: [5,4,3,2,1]
  • Explanation: The linked list 1 -> 2 -> 3 -> 4 -> 5 is reversed to 5 -> 4 -> 3 -> 2 -> 1.

Example 2

  • Input: head = [1,2]
  • Output: [2,1]

Example 3

  • Input: head = []
  • Output: []

Constraints

  • The number of nodes in the list is in the range [0, 5000].
  • -5000 <= Node.val <= 5000

Approaches

2 worked solutions ranked from straightforward to optimal — each with intuition, algorithm, complexity, and verified code in C++, Java, Python, and Go.

Approach 1

Iterative

Intuition

The iterative approach reverses the list in a single pass by maintaining three pointers: previous, current, and next. At each step we save the next node, point the current node backward to the previous node, then advance both previous and current forward by one position. When current reaches nil, previous points to the new head. This runs in O(n) time with O(1) extra space since we only reassign existing pointers.

Algorithm

  1. Initialize `prev` to null and `curr` to `head`.
  2. While `curr` is not null, save `curr.next` in a temporary variable `next`.
  3. Set `curr.next = prev` to reverse the pointer direction.
  4. Move `prev` to `curr` and `curr` to `next`.
  5. When the loop ends, `prev` is the new head of the reversed list. Return `prev`.
TimeO(n)SpaceO(1)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;

        while (curr != nullptr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }

        return prev;
    }
};
Java 21
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;

        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }

        return prev;
    }
}
Python 3.12
def reverseList(head: Optional[ListNode]) -> Optional[ListNode]:
    prev = None
    curr = head

    while curr:
        next_node = curr.next
        curr.next = prev
        prev = curr
        curr = next_node

    return prev
Go 1.26
func reverseList(head *ListNode) *ListNode {
    var prev *ListNode
    curr := head

    for curr != nil {
        next := curr.Next
        curr.Next = prev
        prev = curr
        curr = next
    }

    return prev
}
Approach 2

Recursive

Intuition

The recursive approach reverses the list by first recursing to the end, then rewiring pointers on the way back. The base case is when the list is empty or has one node. For each recursive call, we assume the rest of the list is already reversed. We then make the next node point back to the current node and set the current node's next to null to avoid cycles. The key insight is that after the recursive call, head.next still points to the last node of the now-reversed sublist, so head.next.next = head attaches the current node at the end.

Algorithm

  1. Base case: if `head` is null or `head.next` is null, return `head`.
  2. Recursively reverse the rest of the list: `reversed = reverseList(head.next)`.
  3. Set `head.next.next = head` to make the next node point back to the current node.
  4. Set `head.next = null` to remove the old forward pointer.
  5. Return `reversed` as the new head of the fully reversed list.
TimeO(n)SpaceO(n)

Code (C++ · Java · Python · Go)

C++17
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }

        ListNode* reversed = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;

        return reversed;
    }
};
Java 21
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode reversed = reverseList(head.next);
        head.next.next = head;
        head.next = null;

        return reversed;
    }
}
Python 3.12
def reverseList(head: Optional[ListNode]) -> Optional[ListNode]:
    if not head or not head.next:
        return head

    reversed_head = reverseList(head.next)
    head.next.next = head
    head.next = None

    return reversed_head
Go 1.26
func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    reversed := reverseList(head.Next)
    head.Next.Next = head
    head.Next = nil

    return reversed
}

Frequently asked questions

What is the optimal time complexity of Reverse Linked List?

The most efficient approach in this guide ("Recursive") runs in O(n) time and uses O(n) extra space. Earlier brute-force approaches are slower; see all 2 approaches above for the full progression.

What pattern does Reverse Linked List use?

Reverse Linked List is a easy-level Linked List problem involving Linked List, Recursion. Recognizing the pattern is half the work — see the intuition section above for how to spot it.

Can Reverse Linked List be solved without extra space?

The most space-efficient approach in this guide uses O(n) extra space (excluding the input). If you're aiming for in-place — see the trade-off in the algorithm section above — the brute-force approach uses O(1), while the optimized version uses O(n).

Which programming languages does this Ratta solution support?

Every approach above ships with verified, runnable solutions in C++, Java, Python, and Go. The starter templates in the workspace match the same four languages so you can practice in your interview language of choice.

Original problem: leetcode.com

Loading editor...
Input
head=
[1,2,3,4,5]
Expected Output
[5,4,3,2,1]