Learn how to reverse a doubly linked list

An algorithm to reverse a doubly linked list in javascript.

Example

Input:
10 -> 20 -> 30 -> 40 -> 50

Output:
50 -> 40 -> 30 -> 20 -> 10

We will see three different ways to reverse a doubly-linked list.

By swapping pointers.
Through swapping nodes.
Swapping data.

Method 1: Reversing a doubly linked list by swapping pointers.

As we already know that a doubly linked list uses two different pointers next and prev to track its next and previous sibling nodes.
So to reverse the doubly linked list we will just exchange the pointers, like the next node will become the previous node and previous node will become the next.

// swapping pointer
let reverseDLL = (head) => {
  let temp = null;
  let current = head;
  
  while(current){
    temp = current.prev;
    current.prev = current.next;
    current.next = temp;
    current = current.prev;
  }
  
  if (temp != null) { 
    head = temp.prev; 
  }
}

Input:
let dll = new doubleLinkedList();
dll.append(10);
dll.append(20);
dll.append(30);
dll.append(40);
dll.append(50);
let head = dll.getHead();
reverseDLL(head);

Output:
//Head (Next nodes)
50 -> 40 -> 30 -> 20 -> 10

//Tail (Prev nodes)
50 <- 40 <- 30 <- 20 <-10

Time complexity: O(N).
Space complexity: O(1).

Method 2: Reverse the doubly linked list by swapping the nodes.

In this method we will swap the nodes by exchanging them, Like removing the first node from the head and adding as the last node to the new list.
As we will repeat this for all the node of the list, thus the new list which will be formed will be in the reverse order.
To do that we will use one extra helper function which will be pushing the nodes in the new list.

Check out the below image for better reference on how swapping the nodes work.
Reverse doubly linked list

//Add new node to the given list
let push = (head_ref, new_node) => {
  new_node.prev = null;

  //Add the new node if present
  new_node.next = head_ref;
  
  //Mark the previous node
  if(head_ref){
    head_ref.prev = new_node;
  }
  
  head_ref = new_node;
  
  return head_ref;
}

//swapping nodes
let reverseList = (head_ref) => {
  if(head_ref === null || head_ref.next === null){
    return null;
  }
  
  let new_head = null;
  let current = head_ref;
  let next = null;
  
  //Push all the nodes in the new list
  while(current){
    next = current.next;
    new_head = push(new_head, current);
    current = next;
  }
  
  //Set the head to the reversed new list
  head_ref = new_head;

  return head_ref;
}

Input:
let dll = new doubleLinkedList();
dll.append(10);
dll.append(20);
dll.append(30);
dll.append(40);
dll.append(50);
let head = dll.getHead();
reverseDLL(head);

Output:
//Head (Next nodes)
50 -> 40 -> 30 -> 20 -> 10

//Tail (Prev nodes)
50 <- 40 <- 30 <- 20 <-10

Time complexity: O(N).
Space complexity: O(N).

Method 3: Reversing the double linked list by swapping the data.

In this method we will swap the data of the given list to reverse it.
We will swap the data of the first node with last node, second node with second last node and so on.

//swapping data
let reverseDll = (head) => {
  //Get the left and right end of the list
  let left = head, right = head;
  
  //Move to the right end
  while(right.next){
    right = right.next;
  }
  
  //Swap the data at both the ends
  while(left !== right && left.prev !== right){
    let t = left.element;
    left.element = right.element;
    right.element = t;
    left = left.next;
    right = right.prev;
  }
  
  //Return the reversed list
  return head;
}

Input:
let dll = new doubleLinkedList();
dll.append(10);
dll.append(20);
dll.append(30);
dll.append(40);
dll.append(50);
let head = dll.getHead();
reverseDLL(head);

Output:
//Head (Next nodes)
50 -> 40 -> 30 -> 20 -> 10

//Tail (Prev nodes)
50 <- 40 <- 30 <- 20 <-10