Leetcode - Reverse Linked List(with JavaScript)

Today I am going to show how to solve the Reverse Linked algorithm problem.

Here is the problem:

In this blog I am going to use both the iterative and recursive ways to reverse a single link list.

1. Iterative solution:

First, I’m going to initialize 3 pointers:

• prev -> Because it’a a singly linked list, a node does not have reference to its previous node. That’s why we need prev pointer to store a previous element of the node beforehand.
• curr -> to know which node we are currently at.
• nextTemp -> to store the next node before changing the reference. If we change the current’s next value without saving it, we are going to lose our next pointer in the iteration.

var reverseList = function(head) {
    let prev = null;
    let curr = head;
    let nextTemp = curr.next;

Then, I iterate through all nodes to traverse the list.

var reverseList = function(head) {
    let prev = null;
    let curr = head;
    let nextTemp = null;

    while(curr!= null) {
        nextTemp = curr.next; // As I explained earlier, I save the next pointer in the temp variable.
        curr.next = prev;  // Then I reverse the pointer of the current node to its previous node.
        prev = curr;  //  The previous node becomes the node we are currently at.
        curr = nextTemp;  // And the current nodes becomes the
next node we saved earlier. And we keep iterating.
    }
    return prev // At the end, our previous node will be the head node of the new list. 
};

2. Recursive solution:

I will use the linked list below for explaining this solution:

1 -> 2 -> 3 -> 4 ->null

The first call will be from the main method and it will pass in the head of the list (node 1). This method needs to return a new head (node 5), which is the last element of the linked list.

We therefore need to go all the way to the end of the list, just as we would in recursion. Once we hit that 5 we should hopefully hit our base case, which will then allow us to go backwards and finish up the algorithm.

Like in all recursive methods, we need to have a base case. The base case indicates how this method is going to stop recursively calling itself. Our base is going to include 2 parts. One of them will check if the next node is null. If it is null, then it means we are on the last element, which will be returned as a new head node of the reversed linked list.

var reverseList = function(head) {
    if(head == null || head.next == null) {
        return head
    }
};

Because this is a recursive method, the system returns node 5 back to the previous caller (node 4) and stores it in the head variable.
Now we need to reverse the linked list by making node 5 to point to node 4.

Because we are currently at 4 (head), we need to go to the next node (head.next) and point it back to itself (head.next.next = head).
We want essentially the end of the linked list to point to null. Let’s now point 4 to null by saying node.next = null

This process keeps going until we reverse all nodes.

var reverseList = function(head) {
    if(head == null || head.next == null) {
        return head
    }
    newHead = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return newHead;
};

Comments

[pentacular]

The key insight here ought to be that a linked list satisfies the requirements of a stack.

Which means that you can reverse a linked list by popping off the source list and pushing onto the destination list.

There's no need to introduce cycles by using a back-link.

[Manav Misra]

Could you elaborate with an example? I have been struggling with these concepts for a couple of days now. I went about trying to turn a linked list into an array and reversing it and then building it back into a linked list, but that's definitely not ideal, although it does work for most cases.
The example in this article seems a bit contrived with the .next.next - so it may only apply for 'short lists.'
Any other insight is appreciated as to how we can reliably reverse a linked list (in JS) in a 'clean', modern functional way.

[pentacular]

Using a stack abstraction

const push = (item, list) => ({ item, next: list });
const pop = (list) => [list.next, list.item];
const reverse = (list) => {
  let reversed = null;
  while (list !== null) {
    [list, item] = pop(list);
    reversed = push(reversed, item);
  }
  return reversed;
}
console.log(JSON.stringify(reverse(push(3, push(2, push(1, null))))));

Or, if you prefer recursion

const push = (item, list) => ({ item, next: list });
const reverse = (list, reversed = null) =>
  list === null
    ? reversed
    : reverse(list.next, push(list.item, reversed));
console.log(JSON.stringify(reverse(push(3, push(2, push(1, null))))));

[Manav Misra]

I prefer recursion. Tx.