Merge Sort for Linked Lists | Node Class ; Function to merge sort ; Function to merge two linked lists ; While head1 is not null and head2 is not null ; While head1 is not null ; While head2 is not null ; Find mid using The Tortoise and The Hare approach ; Function to print list ; Driver Code ; Apply merge Sort
class Node { constructor ( val ) { this . data = val ; this . next = null ; } } function mergeSort ( head ) { if ( head . next == null ) return head ; var mid = findMid ( head ) ; var head2 = mid . next ; mid . next = null ; var newHead1 = mergeSort ( head ) ; var newHead2 = mergeSort ( head2 ) ; var finalHead = merge ( newHead1 , newHead2 ) ; return finalHead ; } function merge ( head1 , head2 ) { var merged = new Node ( - 1 ) ; var temp = merged ; while ( head1 != null && head2 != null ) { if ( head1 . data < head2 . data ) { temp . next = head1 ; head1 = head1 . next ; } else { temp . next = head2 ; head2 = head2 . next ; } temp = temp . next ; } while ( head1 != null ) { temp . next = head1 ; head1 = head1 . next ; temp = temp . next ; } while ( head2 != null ) { temp . next = head2 ; head2 = head2 . next ; temp = temp . next ; } return merged . next ; } function findMid ( head ) { var slow = head , fast = head . next ; while ( fast != null && fast . next != null ) { slow = slow . next ; fast = fast . next . next ; } return slow ; } function printList ( head ) { while ( head != null ) { document . write ( head . data + " " ) ; head = head . next ; } } var head = new Node ( 7 ) ; var temp = head ; temp . next = new Node ( 10 ) ; temp = temp . next ; temp . next = new Node ( 5 ) ; temp = temp . next ; temp . next = new Node ( 20 ) ; temp = temp . next ; temp . next = new Node ( 3 ) ; temp = temp . next ; temp . next = new Node ( 2 ) ; temp = temp . next ; head = mergeSort ( head ) ; document . write ( " " ) ; printList ( head ) ;