Program to reverse a linked list using a stack

An algorithm to reverse a single linked list using a stack in Javascript.

Example

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

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

Implementation to reverse a single linked list.

• We will use a temp stack, which will store all the elements of the linked list.
• First we will copy all the elements from the linked list to the stack and then create a new linked list from the elements in the stack.
• As stack follows LIFO (Last In First Out) principle the elements will be stored in reversed order and hence the new linked list will also be created with the elements in reverse order.

let reverseLL = (list) => {
  //Stack to store the list element
  let stack = new Stack();
  
  //Get the head of the list
  let head = list.getHead();
  
  //Copy all the items of the list to the stack
  while(head){
    stack.push(head.element);
    head = head.next;
  }
  
  //Temp list to store the elements in reversed order
  let reversedList = new LinkedList();
  
  //Copy all the elements from the stack to the linkedlist
  while(!stack.isEmpty()){
    reversedList.append(stack.pop());
  }
  
  return reversedList;
}

Input:
let ll = new LinkedList();
ll.append(20);
ll.append(5);
ll.append(30);
ll.append(7);
ll.append(3);
console.log(reverseLL(ll).toArray());

Output:
[3, 7, 30, 5, 20]

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

Time and Space complexity

• As we are copying all the linked list elements into the stack and creating a new list from the stack again, Time complexity is O(n + n) = O(n).
• We are using a stack to store all the elements of the linked list, so Space complexity is O(n).