Insertion Sort for Singly Linked List | javascript program to sort link list using insertion sort ; A utility function to insert a node at the beginning of linked list ; allocate node ; link the old list off the new node ; move the head to povar to the new node ; function to sort a singly linked list using insertion sort ; Initialize sorted linked list ; Traverse the given linked list and insert every node to sorted ; Store next for next iteration ; insert current in sorted linked list ; Update current ; Update head_ref to povar to sorted linked list ; * function to insert a new_node in a Note that this function expects a * pointer to head_ref as this can modify the head of the input linked list * ( similar to push ( ) ) ; Special case for the head end ; Locate the node before the povar of insertion ; Function to prvar linked list ; Driver program to test above functions
var head = null ; var sorted = null ; class node { constructor ( val ) { this . val = val ; this . next = null ; } } function push ( val ) { var newnode = new node ( val ) ; newnode . next = head ; head = newnode ; } function insertionSort ( headref ) { var sorted = null ; var current = headref ; while ( current != null ) { var next = current . next ; sortedInsert ( current ) ; current = next ; } head = sorted ; } function sortedInsert ( newnode ) { if ( sorted == null sorted . val >= newnode . val ) { newnode . next = sorted ; sorted = newnode ; } else { var current = sorted ; while ( current . next != null && current . next . val < newnode . val ) { current = current . next ; } newnode . next = current . next ; current . next = newnode ; } } function printlist ( head ) { while ( head != null ) { document . write ( head . val + " " ) ; head = head . next ; } } push ( 5 ) ; push ( 20 ) ; push ( 4 ) ; push ( 3 ) ; push ( 30 ) ; document . write ( " " ) ; printlist ( head ) ; insertionSort ( head ) ; document . write ( " " ) ; printlist ( sorted ) ;