Alternate Odd and Even Nodes in a Singly Linked List | Structure node ; A utility function to print linked list ; Function to create newNode in a linkedlist ; Function to insert at beginning ; Function to rearrange the odd and even nodes ; Step 1 : Segregate even and odd nodes Step 2 : Split odd and even lists Step 3 : Merge even list into odd list ; Step 1 : Segregate Odd and Even Nodes ; Backup next pointer of temp ; If temp is odd move the node to beginning of list ; Advance Temp Pointer ; Step 2 Split the List into Odd and even ; End the odd List ( Make last node None ) ; Step 3 : Merge Even List into odd ; While both lists are not exhausted Backup next pointers of i and j ; ptr points to the latest node added ; Advance i and j pointers ; Odd list exhausts before even , append remainder of even list to odd . ; The case where even list exhausts before odd list is automatically handled since we merge the even list into the odd list ; Driver Code
class Node : NEW_LINE INDENT def __init__ ( self ) : NEW_LINE INDENT self . data = 0 NEW_LINE self . next = None NEW_LINE DEDENT DEDENT def printList ( node ) : NEW_LINE INDENT while ( node != None ) : NEW_LINE INDENT print ( node . data , end = " ▁ " ) NEW_LINE node = node . next NEW_LINE DEDENT print ( " ▁ " ) NEW_LINE DEDENT def newNode ( key ) : NEW_LINE INDENT temp = Node ( ) NEW_LINE temp . data = key NEW_LINE temp . next = None NEW_LINE return temp NEW_LINE DEDENT def insertBeg ( head , val ) : NEW_LINE INDENT temp = newNode ( val ) NEW_LINE temp . next = head NEW_LINE head = temp NEW_LINE return head NEW_LINE DEDENT def rearrange ( head ) : NEW_LINE INDENT even = None NEW_LINE temp = None NEW_LINE prev_temp = None NEW_LINE i = None NEW_LINE j = None NEW_LINE k = None NEW_LINE l = None NEW_LINE ptr = None NEW_LINE temp = ( head ) . next NEW_LINE prev_temp = head NEW_LINE while ( temp != None ) : NEW_LINE INDENT x = temp . next NEW_LINE if ( temp . data % 2 != 0 ) : NEW_LINE INDENT prev_temp . next = x NEW_LINE temp . next = ( head ) NEW_LINE ( head ) = temp NEW_LINE DEDENT else : NEW_LINE INDENT prev_temp = temp NEW_LINE DEDENT temp = x NEW_LINE DEDENT temp = ( head ) . next NEW_LINE prev_temp = ( head ) NEW_LINE while ( temp != None and temp . data % 2 != 0 ) : NEW_LINE INDENT prev_temp = temp NEW_LINE temp = temp . next NEW_LINE DEDENT even = temp NEW_LINE prev_temp . next = None NEW_LINE i = head NEW_LINE j = even NEW_LINE while ( j != None and i != None ) : NEW_LINE INDENT k = i . next NEW_LINE l = j . next NEW_LINE i . next = j NEW_LINE j . next = k NEW_LINE ptr = j NEW_LINE i = k NEW_LINE j = l NEW_LINE DEDENT if ( i == None ) : NEW_LINE INDENT ptr . next = j NEW_LINE DEDENT return head NEW_LINE DEDENT head = newNode ( 8 ) NEW_LINE head = insertBeg ( head , 7 ) NEW_LINE head = insertBeg ( head , 6 ) NEW_LINE head = insertBeg ( head , 3 ) NEW_LINE head = insertBeg ( head , 5 ) NEW_LINE head = insertBeg ( head , 1 ) NEW_LINE head = insertBeg ( head , 2 ) NEW_LINE head = insertBeg ( head , 10 ) NEW_LINE print ( " Linked ▁ List : " ) NEW_LINE printList ( head ) NEW_LINE print ( " Rearranged ▁ List " ) NEW_LINE head = rearrange ( head ) NEW_LINE printList ( head ) NEW_LINE