Sort the biotonic doubly linked list | Java implementation to sort the biotonic doubly linked list ; a node of the doubly linked list ; Function to reverse a Doubly Linked List ; swap next and prev for all nodes of doubly linked list ; Before changing head , check for the cases like empty list and list with only one node ; Function to merge two sorted doubly linked lists ; If first linked list is empty ; If second linked list is empty ; Pick the smaller value ; function to sort a biotonic doubly linked list ; if list is empty or if it contains a single node only ; if true , then ' current ' is the first node which is smaller than its previous node ; move to the next node ; if true , then list is already sorted ; spilt into two lists , one starting with ' head ' and other starting with ' current ' ; reverse the list starting with ' current ' ; merge the two lists and return the final merged doubly linked list ; Function to insert a node at the beginning of the Doubly Linked List ; allocate node ; put in the data ; since we are adding at the beginning , prev is always null ; link the old list off the new node ; change prev of head node to new node ; move the head to point to the new node ; Function to print nodes in a given doubly linked list ; if list is empty ; Driver Code ; Create the doubly linked list : 2 < .5 < .7 < .12 < .10 < .6 < .4 < .1 ; sort the biotonic DLL
class GFG { static class Node { int data ; Node next ; Node prev ; } static Node reverse ( Node head_ref ) { Node temp = null ; Node current = head_ref ; while ( current != null ) { temp = current . prev ; current . prev = current . next ; current . next = temp ; current = current . prev ; } if ( temp != null ) head_ref = temp . prev ; return head_ref ; } static Node merge ( Node first , Node second ) { if ( first == null ) return second ; if ( second == null ) return first ; if ( first . data < second . data ) { first . next = merge ( first . next , second ) ; first . next . prev = first ; first . prev = null ; return first ; } else { second . next = merge ( first , second . next ) ; second . next . prev = second ; second . prev = null ; return second ; } } static Node sort ( Node head ) { if ( head == null head . next == null ) return head ; Node current = head . next ; while ( current != null ) { if ( current . data < current . prev . data ) break ; current = current . next ; } if ( current == null ) return head ; current . prev . next = null ; current . prev = null ; current = reverse ( current ) ; return merge ( head , current ) ; } static Node push ( Node head_ref , int new_data ) { Node new_node = new Node ( ) ; new_node . data = new_data ; new_node . prev = null ; new_node . next = ( head_ref ) ; if ( ( head_ref ) != null ) ( head_ref ) . prev = new_node ; ( head_ref ) = new_node ; return head_ref ; } static void printList ( Node head ) { if ( head == null ) System . out . println ( " Doubly ▁ Linked ▁ list ▁ empty " ) ; while ( head != null ) { System . out . print ( head . data + " ▁ " ) ; head = head . next ; } } public static void main ( String args [ ] ) { Node head = null ; head = push ( head , 1 ) ; head = push ( head , 4 ) ; head = push ( head , 6 ) ; head = push ( head , 10 ) ; head = push ( head , 12 ) ; head = push ( head , 7 ) ; head = push ( head , 5 ) ; head = push ( head , 2 ) ; System . out . println ( " Original ▁ Doubly ▁ linked ▁ list : n " ) ; printList ( head ) ; head = sort ( head ) ; System . out . println ( " Doubly linked list after sorting : n "); printList ( head ) ; } }