Learn how to reverse a linked list

An algorithm to reverse a single linked list in javascript.

Example

Input:
20 -> 5 -> 30 -> 7 -> 3

Output:
3 -> 7 -> 30 -> 5 -> 20

Implementation to reverse a single linked list.

• We are going to use three different variables prev, current, next because we reversing the list in javascript.
• We will store the next element of the linked list in the next variable and assign the prev variables to the next element, then copy the current to prev and next to current.
• We repeat this for all the elements thus resulting in the reversed linked list.

Checkout the below image for the working of this implementation

let reverse = (head) => {
  let prev = null;
  let current = head;
  let next = null;
  
  while(current !== null){
     next = current.next; 
     current.next = prev; 
     prev = current; 
     current = next;
  }
  
  head = prev; 
  return head; 
}

Input:
let ll = new linkedlist();
ll.append(20);
ll.append(5);
ll.append(30);
ll.append(7);
ll.append(3);
let head = ll.getHead();
//20 -> 5 -> 30 -> 7 -> 3
console.log(reverse(head));

Output:
3 -> 7 -> 30 -> 5 -> 20

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

Time and Space complexity

• We are iterating each element of the list, so Time complexity is O(n).
• We are using constant space, so Space complexity is O(1).