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 null ) ; 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 { constructor ( ) { this . data = 0 ; this . next = null ; } } function printList ( node ) { while ( node != null ) { document . write ( node . data + " " ) ; node = node . next ; } document . write ( " " ) ; } function newNode ( key ) { var temp = new Node ( ) ; temp . data = key ; temp . next = null ; return temp ; } function insertBeg ( head , val ) { var temp = newNode ( val ) ; temp . next = head ; head = temp ; return head ; } function rearrange ( head ) { var even ; var temp , prev_temp ; var i , j , k , l , ptr = null ; temp = ( head ) . next ; prev_temp = head ; while ( temp != null ) { var x = temp . next ; if ( temp . data % 2 != 0 ) { prev_temp . next = x ; temp . next = ( head ) ; ( head ) = temp ; } else { prev_temp = temp ; } temp = x ; } temp = ( head ) . next ; prev_temp = ( head ) ; while ( temp != null && temp . data % 2 != 0 ) { prev_temp = temp ; temp = temp . next ; } even = temp ; prev_temp . next = null ; i = head ; j = even ; while ( j != null && i != null ) { k = i . next ; l = j . next ; i . next = j ; j . next = k ; ptr = j ; i = k ; j = l ; } if ( i == null ) { ptr . next = j ; } return head ; } var head = newNode ( 8 ) ; head = insertBeg ( head , 7 ) ; head = insertBeg ( head , 6 ) ; head = insertBeg ( head , 3 ) ; head = insertBeg ( head , 5 ) ; head = insertBeg ( head , 1 ) ; head = insertBeg ( head , 2 ) ; head = insertBeg ( head , 10 ) ; document . write ( " " ) ; printList ( head ) ; document . write ( " " ) ; head = rearrange ( head ) ; printList ( head ) ;