Insertion Sort for Singly Linked List | Java 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 point 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 point to sorted linked list ; * function to insert a new_node in a list . 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 point of insertion ; Function to print linked list ; Driver program to test above functions
public class LinkedlistIS { node head ; node sorted ; class node { int val ; node next ; public node ( int val ) { this . val = val ; } } void push ( int val ) { node newnode = new node ( val ) ; newnode . next = head ; head = newnode ; } void insertionSort ( node headref ) { sorted = null ; node current = headref ; while ( current != null ) { node next = current . next ; sortedInsert ( current ) ; current = next ; } head = sorted ; } void sortedInsert ( node newnode ) { if ( sorted == null sorted . val >= newnode . val ) { newnode . next = sorted ; sorted = newnode ; } else { node current = sorted ; while ( current . next != null && current . next . val < newnode . val ) { current = current . next ; } newnode . next = current . next ; current . next = newnode ; } } void printlist ( node head ) { while ( head != null ) { System . out . print ( head . val + " ▁ " ) ; head = head . next ; } } public static void main ( String [ ] args ) { LinkedlistIS list = new LinkedlistIS ( ) ; list . push ( 5 ) ; list . push ( 20 ) ; list . push ( 4 ) ; list . push ( 3 ) ; list . push ( 30 ) ; System . out . println ( " Linked ▁ List ▁ before ▁ Sorting . . " ) ; list . printlist ( list . head ) ; list . insertionSort ( list . head ) ; System . out . println ( " LinkedList After sorting "); list . printlist ( list . head ) ; } }