text: Alternate Odd and Even Nodes in a Singly Linked List | Cpp program to rearrange nodes as alternate odd 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
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; struct Node { int data ; struct Node * next ; } ; void printList ( struct Node * node ) { while ( node != NULL ) { cout << node -> data << " ▁ " ; node = node -> next ; } cout << endl ; } Node * newNode ( int key ) { Node * temp = new Node ; temp -> data = key ; temp -> next = NULL ; return temp ; } Node * insertBeg ( Node * head , int val ) { Node * temp = newNode ( val ) ; temp -> next = head ; head = temp ; return head ; } void rearrange ( Node * * head ) { Node * even ; Node * temp , * prev_temp ; Node * i , * j , * k , * l , * ptr ; temp = ( * head ) -> next ; prev_temp = * head ; while ( temp != nullptr ) { Node * 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 != nullptr && temp -> data % 2 != 0 ) { prev_temp = temp ; temp = temp -> next ; } even = temp ; prev_temp -> next = nullptr ; i = * head ; j = even ; while ( j != nullptr && i != nullptr ) { k = i -> next ; l = j -> next ; i -> next = j ; j -> next = k ; ptr = j ; i = k ; j = l ; } if ( i == nullptr ) { ptr -> next = j ; } } int main ( ) { Node * 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 ) ; cout << " Linked ▁ List : " << endl ; printList ( head ) ; cout << " Rearranged ▁ List " << endl ; rearrange ( & head ) ; printList ( head ) ; }