Reverse Linked List

Learn to reverse a singly linked list using both iterative and recursive approaches. Master pointer manipulation fundamentals.

EasyTime O(n) · Space O(1) iterative

Problem statement

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

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

Input:  head = []
Output: []

Approach

Iterative approach

  1. 1
    Initialize pointers. Start with prev = null and current = head.
  2. 2
    Iterate through the list. For each node, save the next node, reverse the current node's pointer to point to prev, then move both pointers forward.
  3. 3
    Return the new head. When iteration completes, prev points to the new head of the reversed list.

Recursive approach

  1. 1
    Base case. If the list is empty or has only one node, return the head.
  2. 2
    Recursive call. Recursively reverse the rest of the list starting from head.next.
  3. 3
    Reverse links. Make the next node point back to the current node, then set the current node's next to null.

Solution

JavaScript
// Definition for singly-linked list node
class ListNode {
    constructor(val, next = null) {
        this.val = val;
        this.next = next;
    }
}

// Iterative Solution
function reverseList(head) {
    let prev = null;
    let current = head;

    while (current !== null) {
        // Save next node
        let nextTemp = current.next;
        // Reverse the pointer
        current.next = prev;
        // Move pointers forward
        prev = current;
        current = nextTemp;
    }

    return prev; // New head
}

// Recursive Solution
function reverseListRecursive(head) {
    // Base case
    if (head === null || head.next === null) {
        return head;
    }

    // Recursive call
    let newHead = reverseListRecursive(head.next);

    // Reverse the links
    head.next.next = head;
    head.next = null;

    return newHead;
}

Time & space complexity

Iterative approach

Time complexity

O(n)

We visit each node exactly once.

Space complexity

O(1)

Only a constant amount of extra space for pointers.

Recursive approach

Time complexity

O(n)

We visit each node exactly once.

Space complexity

O(n)

Due to the recursion call stack, which can go n levels deep.

Discussion

Questions, ideas or a different approach? Join the conversation.