Reverse A Linkedlist In Javascript

Introduction

In the last article, we saw how to create a LinkedList. I highly recommend going through Implementation of Linkedlist article, which will lay the basics for you.

We will cover one of the favorite questions asked in interviews. I have been asked this question in 2 interviews. How to reverse a LinkedList?

Let's say we have a linkedlist as 10 -> 20 -> 30 -> 40 -> 50.
What we want to achieve is this: 50 -> 40 -> 30 -> 20 -> 10.

As you can see above, the whole logic wraps around the concept of reversing the next pointers to the previous pointers, So visually our list would look like this 10 <- 20 <- 30 <- 40 <- 50.

There are a few validations we need to take care of, such as if the list is empty or if the list has only one element.

First, let us use the code from the last article. This code snippet creates a linkedlist with a head node using a constructor and append function adds the element in the back of the list, then the print function prints the list in the simplest format possible.

class LinkedList{
    
    //Creates a linkedlist with passed value.
    constructor(value){ 
        //Creates a head node      
        this.head = new Node(value);

        //As there is only one element in the list, head is also a tail
        this.tail = this.head;

        //Length would be 1
        this.length = 1;
    }  

    //Add the node at the tail of the linkedlist
    append(value){
        //Create a new Node by creating a instance of a Node class
        const newNode = new Node(value);

        // Check if head is present or not, if head is empty creates a head
        if (this.head == null){
            this.head = node;
        } 
        //Else creates a tail
        else{
        //We need to point current tail's next to the newNode
        this.tail.next = newNode;

        //Now make newNode a tail node
        this.tail = newNode;

        //Increase the length by 1
        this.length++;        
        }
        return this;
    }
    
    printList(){
        //Creates an empty array.
        let printArrayList = [];
        //Pointer which points to the head node
        let currentNode = this.head;
        //Start iterating from the first node till you reach the last node
        while(currentNode !== null){
            //Add every node's value to the array
            printArrayList.push(currentNode.value);
            //Point pointer to the next node
            currentNode = currentNode.next;
        }
        //Return the array
        return printArrayList.join(' -> ');
    }   
}

Listing 1: class LinkedList

Let's call these methods and create a linkedlist for us to work with.

console.log('Creating a LinkList at constant time O(1):');
const myLinkedList = new LinkedList(10);
console.log(myLinkedList.printList());
console.log('');

console.log('Appendding Node at constant time O(1):');
myLinkedList.append(20).append(30).append(40).append(50);
console.log(myLinkedList.printList());
console.log('');

Listing 2: Creating a LinkedList with 5 elements

Figure 1: Creating a linkedlist with 5 elements

While reversing a linked list we need to check if the list is empty or if the list only has one element.

//Check if list is null or only has one element
if(!this.head || !this.head.next)
{
   return this.head;
}

Have a previous pointer to point to the previous node,
Have a pointer to point to the current node,

and change the tail of the list, by assigning head to the tail.

//Pointer to the first node: 10
let previousNode = this.head;

//Pointer to the second node: 20
let currentNode = previousNode.next;        

//Now the head will become a tail:
this.tail = this.head;

Loop through the last element, and perform these 4 steps

Pointer to the next node: This node will keep the track of the third node. Once we reverse the pointer of the second element which is 20 in iteration 1, 10 <- 20, We might lose the third element to continue iteration, so keeping a track of the next element.
Reverse the pointer from next to previous node: Instead of 10 -> 20, it will be 10 <- 20
Increment previous node to the next node: which is current node
Increment current node to the next node

//Traverse till the last element
while(currentNode){
    /* 
        This node will keep the track of third node.
        Once we reverse the pointer of second element which is 20 in iteration 1, 10 <- 20,
        We might lose third element to continue iteration, so keeping a track of next element.
    */ 
    let nextNode = currentNode.next;

    // We need reverse a pointer to point to the previous node. 10 <- 20
    currentNode.next = previousNode;

    /* 
        Now we need to move to next 2 elements for comparision.
        So increment previous to current node: 
        previous = 20      
    */
    previousNode = currentNode;

     /*
        Point current node to its next node,
        currentNode = 30.
    */
    currentNode = nextNode;

}

In the last step, point this node's head's next to null, As it is technically a tail node now, and tail node's next point to the null,
In the end, head would be the last node, which will be the previous node by the time it finishes the loop.
```
this.head.next = null;
this.head = previousNode;
```

Following listing is the whole code snippet to reverse a linkedlist.

reverseList(){
    if(!this.head || !this.head.next)
    {
        return this.head;
    }
    let previousNode = this.head;
    let currentNode = previousNode.next;        
    this.tail = this.head;
    while(currentNode){

        let nextNode = currentNode.next;
        currentNode.next = previousNode;
        previousNode = currentNode;
        currentNode = nextNode;

    }
    this.head.next = null;
    this.head = previousNode;
    return this;
}

Listing 3

Figure 2 shows what output would look like.

Figure 2: Reversed linkedlist

Approach 2: Create a method that accepts linkedlist as a parameter and then returns the reverse linkedlist.

What if you need a function that takes linkedlist as parameter and then reverse it. Well logic would be exactly same, only change is we don't have to worry about head and tail pointers.

function reverseLinkedList(linkedlist) {
    if(!linkedlist){
        return linkedlist;
    }
    var currentNode = linkedlist.head;
    var previousNode = null;
    var nextNode = null;
    while(currentNode != null) {
        /* 
            This node will keep the track of third node.
            Once we reverse the pointer of second element which is 20 in iteration 1, 10 <- 20,
            We might lose third element to continue iteration, so keeping a track of next element.
        */ 
        nextNode = currentNode.next;

        // We need reverse a pointer to point to the previous node. 10 <- 20
        currentNode.next = previousNode;

        /* 
            Now we need to move to next 2 elements for comparision.
            So increment previousNode to current node: 
            previousNode = 20      
        */
        previousNode = currentNode;
        
        /*
            Point current node to its next node,
            currentNode = 30.
        */
        currentNode = nextNode;
    }
    return previousNode; 
}

Listing 4: Approach 2

Let's call this method,

console.log('Creating a LinkList at constant time O(1):');
const myLinkedListTwo = new LinkedList(1);
console.log(myLinkedListTwo.printList());
console.log('');

console.log('Appendding Node at constant time O(1):');
myLinkedListTwo.append(2).append(3).append(4).append(5);
console.log(myLinkedListTwo.printList());
console.log('');

console.log(reverseLinkedList(myLinkedListTwo));

And drum roll please, and the output is.

Figure 3: Output of approach 2

Summary

In this article, we learned how to create a linkedlist, how to print a linkedlist and how to reverse a linkedlist.