LeetCode 206: Reverse Linked List (JavaScript) | Iterative and Recursive Solutions Explained

Reverse Linked List

Problem Description

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: []

 

Constraints:

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

 

Follow-up: A linked list can be reversed either iteratively or recursively. Could you implement both?

Why this problem matters

The "Reverse Linked List" problem is the foundational rite of passage for understanding pointer manipulation. It is frequently asked in fundamental technical interviews at companies like Google, Amazon, and Microsoft. Mastering this problem ensures you understand:

• How references/pointers work in memory.

• How to update links without breaking or losing access to the rest of the data structure.

• The foundational mechanics required for more advanced problems like Palindrome Linked List or Reverse Nodes in k-Group

Intuition

A singly linked list is a one-way street: each node only knows about the next node, not the previous one. To reverse it, we must make every node point to its predecessor instead of its successor.

The challenge is that if we immediately change a node's pointer (curr.next = prev), we lose the reference to the rest of the remaining list. To prevent losing our data, we must temporarily store the next node (next = curr.next) before changing the direction of the arrow.

Dry run

Let's trace the iterative approach using a sample list: 1 -> 2 -> 3 -> null.

We initialize prev = null and curr = head (1).

Step	Initial State	Operation	State After Step	Pointers Updated
Setup	1 -> 2 -> 3 -> null	Initialize pointers	prev = null, curr = 1	None
Iteration 1	curr is 1	Store next node: next = 2 Reverse connection: 1.next = null	prev = 1, curr = 2	1 -> null
Iteration 2	curr is 2	Store next node: next = 3 Reverse connection: 2.next = 1	prev = 2, curr = 3	2 -> 1 -> null
Iteration 3	curr is 3	Store next node: next = null Reverse connection: 3.next = 2	prev = 3, curr = null	3 -> 2 -> 1 -> null

The loop terminates because curr becomes null. We return prev, which correctly points to 3, our new head.

Iterative solution

The iterative approach employs a multi-pointer strategy to cleanly step through the list and change directions dynamically.

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 * this.val = (val===undefined ? 0 : val)
 * this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    // Base case: if list is empty or has only one element
    if (head == null || head.next == null) {
        return head;
    }
    
    let prev = null;
    let curr = head;
    
    while (curr !== null) {
        let nextNode = curr.next; // Save the rest of the list
        curr.next = prev;         // Reverse the link
        prev = curr;              // Move prev one step forward
        curr = nextNode;          // Move curr one step forward
    }
    
    return prev; // prev will be standing at the new head node
};

Complexity Analysis

• Time Complexity: $\mathcal{O}(N)$ — We traverse the linked list exactly once, where $N$ is the number of nodes.

• Space Complexity: $\mathcal{O}(1)$ — We are manipulating existing node pointers using constant extra memory space.

Resources:

https://github.com/PraveenMistry/leetCode

https://medium.com/@praveenmistry/linked-list-javascript-part-3-1-d504f0c9b54e

https://medium.com/@praveenmistry/doubly-linked-list-javascript-part-3-2-1209068fb788

Conclusion

That’s all folks! In this post, we solved LeetCode problem #206. Reverse Linked List

I hope you have enjoyed this post. Feel free to share your thoughts on this.

You can find the complete source code on my GitHub repository. If you like what you learn. feel free to fork 🔪 and star ⭐ it.

In this blog, I have tried to solve leetcode questions & present the most important points to consider when improving Data structure and logic,  feel free to add, edit, comment, or ask. For more information please reach me here
Happy coding!

Recursive solution

The recursive approach leverages the call stack to reach the end of the list first, and then reverses the pointers as the recursion unwinds ("pops" off the stack).

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseListRecursive = function(head) {
    // Base Case
    if (!head || !head.next) {
        return head;
    }

    // Recurse down to the end of the list
    let newHead = reverseListRecursive(head.next);
    
    // Reverse the link direction
    head.next.next = head; 
    head.next = null;      // Disconnect original forward link to avoid cycles
    
    return newHead;
};

Trace Breakdown:

Given 1 -> 2 -> 3 -> null:

1. reverseList(1) calls reverseList(2)

2. reverseList(2) calls reverseList(3)

3. reverseList(3) hits the base case and returns 3 (newHead = 3)

4. Unwinding to reverseList(2) execution context:

   • head is 2. head.next is 3.

   • head.next.next = head maps 3.next = 2.

   • head.next = null maps 2.next = null.

   • List becomes: 1 -> 2 <- 3

5. Unwinding to reverseList(1) execution context:

   • head is 1. head.next is 2.

   • head.next.next = head maps 2.next = 1.

   • head.next = null maps 1.next = null.

   • List becomes: null <- 1 <- 2 <- 3



Complexity Analysis

• Time Complexity: $\mathcal{O}(N)$ — Every node is visited once.

• Space Complexity: $\mathcal{O}(N)$ — The system call stack uses space proportional to the length of the list due to recursive function frames.

Common mistakes

• Forgetting to break the old connection: If you don't set head.next = null in the recursive variant or handle the initial head node cleanly, you will form a pointer cycle (e.g., 1 -> 2 and 2 -> 1), causing an infinite loop.

• Losing the rest of the list: Writing curr.next = prev before capturing curr.next in a temporary variable instantly breaks your reference map, stranding the remaining unvisited nodes in memory.

• Returning the wrong head: Accidentally returning curr instead of prev at the end of the iterative loop. When the loop ends, curr points to null, meaning you will return an empty list.

Interview follow-ups

If you solve this smoothly in an interview, expect these follow-up adjustments:

1. Can you reverse only a specific sub-segment of the list? (e.g., from position $m$ to $n$). See LeetCode 92: Reverse Linked List II.

2. What if the list is a Doubly Linked List? You would need to swap both the .next and .prev pointers for every node during traversal.

3. Can you do it recursively without using $\mathcal{O}(N)$ call stack space? Yes, by using an optimized Tail Recursion strategy passing the prev state down through parameters (though JavaScript engines vary in tail-call optimization support).

Related problems

Accelerate your learning path by practicing these next:

• LeetCode 92 - Reverse Linked List II (Medium)

• LeetCode 234 - Palindrome Linked List (Easy)

• LeetCode 24 - Swap Nodes in Pairs (Medium)

• LeetCode 25 - Reverse Nodes in k-Group (Hard)

FAQ

Q: Which solution is preferred in a production environment?

A: The Iterative solution is highly preferred. Because it runs in $\mathcal{O}(1)$ auxiliary space, it eliminates the risk of running into a Maximum call stack size exceeded error if your application encounters a long linked list (e.g., thousands of nodes).

Q: Why does the recursive method use $\mathcal{O}(N)$ space if no new objects are declared?

A: Memory allocation isn't restricted to your explicit code definitions. The system runtime creates a nested layer of Execution Contexts on your memory stack for every pending function call, consuming additional stack memory space linearly with the data size.

Resources & Links

• Complete repository code: GitHub — PraveenMistry/leetCode

• Deep Dive Tutorial: Medium — Linked List JavaScript Part 3.1

• Learn Doubly Linked Lists: Medium — Doubly Linked List JavaScript Part 3.2

Happy Coding!