Sorting a linked list

An algorithm for sorting a linked list in javascript.

We will implement the insertion sort algorithm with linked list to sort the list in ascending or descending order.

Example

Input:
10 -> 5 -> 22 -> 3 -> 17 -> 10

Output:
3 -> 5 -> 10 -> 10 -> 17 -> 22

Implementation for sorting a linked list

• We will use a temporary node to sort the linked list.
• We will create two functions. First, which will iterate the list and Second, which will sort the elements till the given element of the first loop.
• The implementation is same as we do the insertion sort for arrays, the only thing here is we will be using one extra node which will help us to swap the list.

//Node class
class Node{
    constructor(elm, next = null){
      this.element = elm;
      this.next = next;
    }
}

//Main function
let insertionSort = (head) => {
  let result = null;
  let current = head;
  let next;
  
  //Iterate the loop
  while(current !== null){
    next = current.next;
    
    //Sort the linked list till the current element and store it
    result = sortedInsert(result, current);
    current = next;
  }
  
 //Return the sorted list
 return result;
}

//Function to sort the list
let sortedInsert = (sorted, newNode) => {    
    //Temporary node to swap the elements 
    let temp = new Node();
    let current = temp;
    temp.next = sorted;
    
    //Sort the list based on the specified order
    while(current.next !== null && current.next.element < newNode.element){
      current = current.next;
    }
    
    //Swap the elements
    newNode.next = current.next;
    current.next = newNode;
    
    //Return the sorted list.
    return temp.next;
}

Input:
let ll = new LinkedList();
ll.append(10);
ll.append(5);
ll.append(22);
ll.append(3);
ll.append(17);
ll.append(10);

//Get the head
let toSort = ll.getHead();

//Sort the list
let sorted = insertionSort(toSort);

//Print the sorted list
while(sorted !== null){
  console.log(sorted.element);
  sorted = sorted.next;
}

Output:
3
5
10
10
17
22

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

Time and Space complexity

• We are using two different loops to the sort the linked list like n * (n - 1) * (n - 2), so Time complexity is O(n ^ 2).
• We are using one extra node (constant space), so Space complexity is O(1).