Rearrange a linked list such that all even and odd positioned nodes are together | Linked List Node ; A utility function to create a new node ; Rearranges given linked list such that all even positioned nodes are before odd positioned . Returns new head of linked List . ; Corner case ; Initialize first nodes of even and odd lists ; Remember the first node of even list so that we can connect the even list at the end of odd list . ; If there are no more nodes , then connect first node of even list to the last node of odd list ; Connecting odd nodes ; If there are NO more even nodes after current odd . ; Connecting even nodes ; A utility function to print a linked list ; Function to insert a new node at the beginning ; Driver code
class Node : NEW_LINE INDENT def __init__ ( self , d ) : NEW_LINE INDENT self . data = d NEW_LINE self . next = None NEW_LINE DEDENT DEDENT class LinkedList : NEW_LINE INDENT def __init__ ( self ) : NEW_LINE INDENT self . head = None NEW_LINE DEDENT def newNode ( self , key ) : NEW_LINE INDENT temp = Node ( key ) NEW_LINE self . next = None NEW_LINE return temp NEW_LINE DEDENT def rearrangeEvenOdd ( self , head ) : NEW_LINE INDENT if ( self . head == None ) : NEW_LINE INDENT return None NEW_LINE DEDENT odd = self . head NEW_LINE even = self . head . next NEW_LINE evenFirst = even NEW_LINE while ( 1 == 1 ) : NEW_LINE INDENT if ( odd == None or even == None or ( even . next ) == None ) : NEW_LINE INDENT odd . next = evenFirst NEW_LINE break NEW_LINE DEDENT odd . next = even . next NEW_LINE odd = even . next NEW_LINE if ( odd . next == None ) : NEW_LINE INDENT even . next = None NEW_LINE odd . next = evenFirst NEW_LINE break NEW_LINE DEDENT even . next = odd . next NEW_LINE even = odd . next NEW_LINE DEDENT return head NEW_LINE DEDENT def printlist ( self , node ) : NEW_LINE INDENT while ( node != None ) : NEW_LINE INDENT print ( node . data , end = " " ) NEW_LINE print ( " - > " , end = " " ) NEW_LINE node = node . next NEW_LINE DEDENT print ( " NULL " ) NEW_LINE DEDENT def push ( self , new_data ) : NEW_LINE INDENT new_node = Node ( new_data ) NEW_LINE new_node . next = self . head NEW_LINE self . head = new_node NEW_LINE DEDENT DEDENT ll = LinkedList ( ) NEW_LINE ll . push ( 5 ) NEW_LINE ll . push ( 4 ) NEW_LINE ll . push ( 3 ) NEW_LINE ll . push ( 2 ) NEW_LINE ll . push ( 1 ) NEW_LINE print ( " Given ▁ Linked ▁ List " ) NEW_LINE ll . printlist ( ll . head ) NEW_LINE start = ll . rearrangeEvenOdd ( ll . head ) NEW_LINE print ( " Modified Linked List " ) NEW_LINE ll . printlist ( start ) NEW_LINE