Sorted merge of two sorted doubly circular linked lists | Python3 implementation for Sorted merge of two sorted doubly circular linked list ; A utility function to insert a new node at the beginning of doubly circular linked list ; allocate space ; put in the data ; if list is empty ; pointer points to last Node ; setting up previous and next of new node ; update next and previous pointers of head_ref and last . ; update head_ref pointer ; function for Sorted merge of two sorted doubly linked list ; If first list is empty ; If second list is empty ; Pick the smaller value and adjust the links ; function for Sorted merge of two sorted doubly circular linked list ; if 1 st list is empty ; if 2 nd list is empty ; get pointer to the node which will be the last node of the final list last_node ; store None to the ' next ' link of the last nodes of the two lists ; sorted merge of head1 and head2 ; ' prev ' of 1 st node pointing the last node ' next ' of last node pointing to 1 st node ; function to print the list ; Driver Code ; list 1 : ; list 2 :
import math NEW_LINE class Node : NEW_LINE INDENT def __init__ ( self , data ) : NEW_LINE INDENT self . data = data NEW_LINE self . next = None NEW_LINE self . prev = None NEW_LINE DEDENT DEDENT def insert ( head_ref , data ) : NEW_LINE INDENT new_node = Node ( data ) NEW_LINE new_node . data = data NEW_LINE if ( head_ref == None ) : NEW_LINE INDENT new_node . next = new_node NEW_LINE new_node . prev = new_node NEW_LINE DEDENT else : NEW_LINE INDENT last = head_ref . prev NEW_LINE new_node . next = head_ref NEW_LINE new_node . prev = last NEW_LINE last . next = new_node NEW_LINE head_ref . prev = new_node NEW_LINE DEDENT head_ref = new_node NEW_LINE return head_ref NEW_LINE DEDENT def merge ( first , second ) : NEW_LINE INDENT if ( first == None ) : NEW_LINE INDENT return second NEW_LINE DEDENT if ( second == None ) : NEW_LINE INDENT return first NEW_LINE DEDENT if ( first . data < second . data ) : NEW_LINE INDENT first . next = merge ( first . next , second ) NEW_LINE first . next . prev = first NEW_LINE first . prev = None NEW_LINE return first NEW_LINE DEDENT else : NEW_LINE INDENT second . next = merge ( first , second . next ) NEW_LINE second . next . prev = second NEW_LINE second . prev = None NEW_LINE return second NEW_LINE DEDENT DEDENT def mergeUtil ( head1 , head2 ) : NEW_LINE INDENT if ( head1 == None ) : NEW_LINE INDENT return head2 NEW_LINE DEDENT if ( head2 == None ) : NEW_LINE INDENT return head1 NEW_LINE DEDENT if ( head1 . prev . data < head2 . prev . data ) : NEW_LINE INDENT last_node = head2 . prev NEW_LINE DEDENT else : NEW_LINE INDENT last_node = head1 . prev NEW_LINE DEDENT head1 . prev . next = None NEW_LINE head2 . prev . next = None NEW_LINE finalHead = merge ( head1 , head2 ) NEW_LINE finalHead . prev = last_node NEW_LINE last_node . next = finalHead NEW_LINE return finalHead NEW_LINE DEDENT def printList ( head ) : NEW_LINE INDENT temp = head NEW_LINE while ( temp . next != head ) : NEW_LINE INDENT print ( temp . data , end = " ▁ " ) NEW_LINE temp = temp . next NEW_LINE DEDENT print ( temp . data , end = " ▁ " ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT head1 = None NEW_LINE head2 = None NEW_LINE head1 = insert ( head1 , 8 ) NEW_LINE head1 = insert ( head1 , 5 ) NEW_LINE head1 = insert ( head1 , 3 ) NEW_LINE head1 = insert ( head1 , 1 ) NEW_LINE head2 = insert ( head2 , 11 ) NEW_LINE head2 = insert ( head2 , 9 ) NEW_LINE head2 = insert ( head2 , 7 ) NEW_LINE head2 = insert ( head2 , 2 ) NEW_LINE newHead = mergeUtil ( head1 , head2 ) NEW_LINE print ( " Final ▁ Sorted ▁ List : ▁ " , end = " " ) NEW_LINE printList ( newHead ) NEW_LINE DEDENT