Reverse Linked List

Reversing a linked list is a common problem asked in the interviews. It requires rearranging the pointers of each node to reverse the order of the list.

In this article, we will explore the Iterative and Recursive approaches to solve this problem and their implementation in JavaScript. But before that let’s see the problem statement.

Problem Statement:

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

So, let’s dive in and explore how we can solve this problem.

---

Approach 1: Iterative

We iterate through the original list, reversing the pointers of each node iteratively. By updating the pointers correctly, we gradually build the reversed list.

1. Initialize three pointers: prev as null, current as the head, and next.

2. Iterate through the linked list until current is null.

3. Within each iteration, store the next node in the next pointer.

4. Update the next pointer of the current node to point to the previous node (prev).

5. Update the prev pointer to the current node.

6. Move the current pointer to the next node (next).

7. Finally, update the head pointer to the last node visited (prev).

// ES6 Arrow Function
const reverseList = head => {
    let prev = null;
    let current = head;

    while(current !== null) {
        let next = current.next;
        current.next = prev;
        prev = current;
        current = next;
    }

    return prev;
}

Time Complexity: O(N)

We visit each node in the linked list once and perform a constant amount of operations. Therefore the time complexity is directly proportional to number of nodes in the linked list.

Space Complexity: O(1)

We don’t use any extra space to solve this problem. So the space complexity is constant despite the length of the linked list.

---

Approach 2: Recursion

1. Base case: If the head is null or the head's next node is null, return the head.

2. Recursively call the function for the rest of the linked list from the second node.

3. Reverse the next node’s next pointer to point to the current node.

4. Set the current node’s next pointer to null.

5. Return the reversed linked list.

// ES6 Arrow Function
const reverseList = head => {
    if(head === null || head.next === null) return head;

    let reversedList = reverseList(head.next);
    head.next.next = head;
    head.next = null;

    return reversedList;
}

Time Complexity: O(N)

Each recursive call processes one node of the linked list. Since we make recursive calls for each node except the last one, the number of recursive calls is equal to the number of nodes in the linked list. Therefore, the time complexity will be linear.

Space Complexity: O(N)

The space complexity of the recursive approach is determined by the recursion stack. Each recursive call adds a new frame to the stack, which contains the local variables and return address. In the worst case, when the linked list is completely unrolled, there will be a maximum of ’n’ recursive calls on the stack. Therefore the space complexity of this approach is linear as well. As the space usage grows linearly with the number of nodes in the linked list.

---

And there you have it guys! We’ve explored two different approaches, saw their implementation, and hopefully had some fun along the way. I hope this article has provided you with valuable insights and helped you better understand the different approaches to solving this problem. Happy coding!

Problem - Leetcode 206