All Problems
EasyLinked ListRecursion

Reverse Linked List

Time Complexity
O(n)
Space Complexity
O(1) iterative / O(n) recursive

📋Problem Statement

Given the head of a singly linked list, reverse the list, and return the reversed list. The reversal should be done in-place.

💡Examples

1Example 1
Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
Explanation: The list is reversed so that 5 becomes the new head.
2Example 2
Input: head = [1,2]
Output: [2,1]
Explanation: Simple two-node reversal.
3Example 3
Input: head = []
Output: []
Explanation: Empty list remains empty.

⚠️Constraints

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

🧠Approach

There are two classic approaches: **Iterative (Recommended):** 1. Use three pointers: prev (null), curr (head), next (temp) 2. For each node: - Save the next node - Point current node's next to prev - Move prev to current - Move current to saved next 3. Return prev (new head) **Recursive:** 1. Base case: if head is null or single node, return head 2. Recursively reverse the rest of the list 3. Make the next node point back to current node 4. Set current node's next to null 5. Return the new head from recursion The iterative approach uses O(1) space, while recursive uses O(n) call stack.

✨Solution

// Iterative Approach
function reverseList(head) {
    let prev = null;
    let curr = head;
    
    while (curr !== null) {
        const next = curr.next;  // Save next node
        curr.next = prev;         // Reverse the link
        prev = curr;              // Move prev forward
        curr = next;              // Move curr forward
    }
    
    return prev;
}

// Recursive Approach
function reverseListRecursive(head) {
    if (head === null || head.next === null) {
        return head;
    }
    
    const newHead = reverseListRecursive(head.next);
    head.next.next = head;
    head.next = null;
    
    return newHead;
}

🎯Key Points

  • 1Iterative approach is preferred for O(1) space complexity
  • 2The key is using a 'prev' pointer to track the reversed portion
  • 3Always save 'next' before modifying the current node's pointer
  • 4Recursive approach is elegant but uses O(n) stack space
  • 5This is a fundamental linked list operation - master it!
Browse More Problems