Problem Statement #

Reverse a singly linked list.

Example:

Input:  1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

Solution #

var reverseList = function(head) {
    //iterate through
    //keep track of prior and next
    //set next to prior, and move to next node
    let curr = head;
    let prev = null;
    let next = null;

    while (curr != null) {
        next = curr.next; //keep track of next
        curr.next = prev; //set to prior
        prev = curr; //set new prev for next iteration
        curr = next; //move to next node
    }
    //return new head
    return prev; //since curr is null
};

Approach #

This is a classic linked list problem that appears frequently in coding interviews. The challenge lies in reversing the pointers without losing track of the remaining nodes in the list.

Understanding the Problem #

The key insight is that we need to reverse what each node points to. However, if we simply change a node’s pointer without preparation, we’ll lose access to the rest of the list. For example, if we make node 2 point to node 1, we can no longer reach node 3 through node 2.

The solution is to temporarily keep track of both the previous and next nodes as we traverse the list.

Algorithm Steps #

At each iteration of the loop, we perform these operations in order:

1. Keep track of the next node by assigning curr.next to next
2. Reverse the current pointer by setting curr.next to prev
3. Update prev for the next iteration by setting prev to curr
4. Move to the next node by setting curr to next

By the time we finish iterating, all the pointers have been reversed, and prev points to the new head of the linked list (which was the original tail).

Visual Example #

Let’s trace through the algorithm with the list 1->2->3->NULL:

Initial state:

curr = 1, prev = null, next = null
List: 1->2->3->NULL

First iteration:

next = 2 (save reference to next node)
1->null (reverse current node's pointer)
prev = 1, curr = 2
List state: null<-1  2->3->NULL

Second iteration:

next = 3
2->1 (reverse current node's pointer)
prev = 2, curr = 3
List state: null<-1<-2  3->NULL

Third iteration:

next = null
3->2 (reverse current node's pointer)
prev = 3, curr = null
List state: null<-1<-2<-3

Loop ends (curr is null), return prev which points to 3, the new head.

Complexity Analysis #

Time Complexity: O(n) where n is the number of nodes in the linked list. We visit each node exactly once.

Space Complexity: O(1) as we only use a constant amount of extra space for the three pointer variables (curr, prev, next).

Alternative Approach: Recursive Solution #

While the iterative approach is more intuitive and space-efficient, the problem can also be solved recursively:

var reverseListRecursive = function(head) {
    // Base case: empty list or single node
    if (head === null || head.next === null) {
        return head;
    }

    // Recursively reverse the rest of the list
    const newHead = reverseListRecursive(head.next);

    // Reverse the current node's pointer
    head.next.next = head;
    head.next = null;

    return newHead;
};

The recursive solution has the same time complexity O(n) but uses O(n) space due to the recursion stack, making it less efficient than the iterative approach.

Key Takeaways #

• The dummy variable pattern (using prev, curr, next) is essential for in-place linked list manipulation
• Always preserve references to nodes before changing pointers
• The iterative approach is preferred for this problem due to O(1) space complexity
• Understanding this problem is fundamental for more complex linked list operations

This problem is a building block for many other linked list algorithms and demonstrates the importance of careful pointer manipulation in data structure problems.