Reverse a Linked List

Reverse a singly linked list in-place and return the new head.

Language Selection

Choose your preferred programming language

Showing: Python

Reverse a Linked List

Problem Statement

Given the head of a singly linked list, reverse the list and return the head of the reversed list.

A singly linked list node is typically defined as:

  • val: the value stored in the node
  • next: pointer/reference to the next node (or null)

Examples

Example 1

  • Input: head = [1,2,3,4,5]
  • Output: [5,4,3,2,1]

Example 2

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

Example 3 (edge case: empty list)

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

Constraints

  • Number of nodes is in the range [0, 5000] on LeetCode.
  • Values can be negative; value ranges don’t affect the logic.
  • Follow-up: implement both iterative and recursive solutions.

Note: Other platforms may allow up to 10^5 nodes, where recursion can overflow the call stack.

Intuition — what insight unlocks the solution?

Reversing a linked list is fundamentally about rewiring pointers, not swapping values.

If you traverse the list from left to right, each node currently points forward. To reverse it, each node must be changed to point to the node before it.

The key pattern is in-place pointer reversal using a small fixed set of pointers:

  • prev: head of the already-reversed prefix
  • curr: the node we’re currently reversing
  • next: saved pointer to avoid losing the rest of the list

This is a classic linked-list pointer manipulation problem.

Approach

Approach 1: Brute force (not in-place)

Idea: Copy values into an array, reverse the array, then write values back (or build a new reversed list).

  • Pros: simple
  • Cons: uses extra memory; often not what interviewers want

Steps (value-copy variant):

  1. Traverse list, push values to an array.
  2. Reverse the array.
  3. Traverse list again, overwrite node values.

Time: O(n); Space: O(n).

Approach 2: Recursive reversal (clean but uses call stack)

Idea: Reverse the rest of the list, then fix the pointers on the way back.

If head -> ... -> tail, after reversing the sublist starting at head.next, we can do:

  • head.next.next = head (make next node point back to head)
  • head.next = null (head becomes new tail)

Time: O(n); Space: O(n) due to recursion depth.

On very large lists (e.g., 10^5 nodes), recursion may cause stack overflow.

Approach 3: Iterative in-place reversal (optimal)

Invariant:

  • prev always points to the reversed prefix
  • curr points to the next node to reverse
  • the remainder of the list is preserved via next

Steps:

  1. Initialize prev = null, curr = head.
  2. While curr != null:
    • Save next = curr.next (so we don’t lose the remainder)
    • Reverse pointer: curr.next = prev
    • Advance: prev = curr, curr = next
  3. When the loop ends, prev is the new head (because curr is null).

This rewires each next pointer exactly once.

Solution

Python:

from typing import Optional

class ListNode:
    def __init__(self, val: int = 0, next: Optional["ListNode"] = None):
        self.val = val
        self.next = next

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        """Iterative in-place reversal: O(n) time, O(1) extra space."""
        prev = None
        curr = head

        while curr is not None:
            nxt = curr.next      # save remainder
            curr.next = prev     # reverse pointer
            prev = curr          # advance prev
            curr = nxt           # advance curr

        return prev

    def reverseListRecursive(self, head: Optional[ListNode]) -> Optional[ListNode]:
        """Recursive reversal: O(n) time, O(n) call stack space."""
        if head is None or head.next is None:
            return head

        new_head = self.reverseListRecursive(head.next)
        head.next.next = head
        head.next = None
        return new_head

Java:

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
    // Iterative in-place reversal
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;

        while (curr != null) {
            ListNode next = curr.next; // save remainder
            curr.next = prev;          // reverse pointer
            prev = curr;               // advance prev
            curr = next;               // advance curr
        }

        return prev;
    }

    // Recursive reversal (follow-up)
    public ListNode reverseListRecursive(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode newHead = reverseListRecursive(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

Go:

package main

type ListNode struct {
	Val  int
	Next *ListNode
}

// Iterative in-place reversal
func reverseList(head *ListNode) *ListNode {
	var prev *ListNode = nil
	curr := head

	for curr != nil {
		next := curr.Next // save remainder
		curr.Next = prev  // reverse pointer
		prev = curr       // advance prev
		curr = next       // advance curr
	}

	return prev
}

// Recursive reversal (follow-up)
func reverseListRecursive(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	newHead := reverseListRecursive(head.Next)
	head.Next.Next = head
	head.Next = nil
	return newHead
}

JavaScript:

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *   this.val = (val===undefined ? 0 : val)
 *   this.next = (next===undefined ? null : next)
 * }
 */

class Solution {
  // Iterative in-place reversal
  reverseList(head) {
    let prev = null;
    let curr = head;

    while (curr !== null) {
      const next = curr.next; // save remainder
      curr.next = prev;       // reverse pointer
      prev = curr;            // advance prev
      curr = next;            // advance curr
    }

    return prev;
  }

  // Recursive reversal (follow-up)
  reverseListRecursive(head) {
    if (head === null || head.next === null) return head;

    const newHead = this.reverseListRecursive(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
  }
}

C#:

public class ListNode {
    public int val;
    public ListNode next;
    public ListNode(int val = 0, ListNode next = null) {
        this.val = val;
        this.next = next;
    }
}

public class Solution {
    // Iterative in-place reversal
    public ListNode ReverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;

        while (curr != null) {
            ListNode next = curr.next; // save remainder
            curr.next = prev;          // reverse pointer
            prev = curr;               // advance prev
            curr = next;               // advance curr
        }

        return prev;
    }

    // Recursive reversal (follow-up)
    public ListNode ReverseListRecursive(ListNode head) {
        if (head == null || head.next == null) return head;

        ListNode newHead = ReverseListRecursive(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

Complexity Analysis

Iterative (optimal)

  • Time: O(n) because we traverse the list once and rewire each node’s next pointer exactly once.
  • Space: O(1) because we only use a constant number of pointers (prev, curr, next).

Recursive

  • Time: O(n) because each node is visited once.
  • Space: O(n) due to recursion call stack depth (one stack frame per node).

Brute force (array / rebuild)

  • Time: O(n)
  • Space: O(n) for the extra array or newly allocated nodes.

Common Mistakes

  1. Losing the rest of the list

    • Bug: doing curr.next = prev before saving the original curr.next.
    • Fix: always store next = curr.next first.

  2. Returning the wrong pointer

    • At the end of the loop, curr is null. The new head is prev.

  3. Creating a cycle accidentally

    • Incorrect update order can cause nodes to still point forward while also pointing backward.

  4. Not handling head = null (empty list)

    • Must return null / None.

  5. Using recursion on very large inputs

    • Can stack overflow on platforms with n up to 10^5.

Related / Follow-up Problems

  • Reverse Linked List II (reverse a sublist)
  • Palindrome Linked List (often uses reversal of the second half)
  • Reverse Nodes in k-Group (harder reversal variant)
  • Maximum Twin Sum of a Linked List