Rearrange a linked list such that all even and odd positioned nodes are together | C ++ program to rearrange a linked list in such a way that all odd positioned node are stored before all even positioned nodes ; 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 ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; class Node { public : int data ; Node * next ; } ; Node * newNode ( int key ) { Node * temp = new Node ; temp -> data = key ; temp -> next = NULL ; return temp ; } Node * rearrangeEvenOdd ( Node * head ) { if ( head == NULL ) return NULL ; Node * odd = head ; Node * even = head -> next ; Node * evenFirst = even ; while ( 1 ) { if ( ! odd || ! even || ! ( even -> next ) ) { odd -> next = evenFirst ; break ; } odd -> next = even -> next ; odd = even -> next ; if ( odd -> next == NULL ) { even -> next = NULL ; odd -> next = evenFirst ; break ; } even -> next = odd -> next ; even = odd -> next ; } return head ; } void printlist ( Node * node ) { while ( node != NULL ) { cout << node -> data << " - > " ; node = node -> next ; } cout << " NULL " << endl ; } int main ( void ) { Node * head = newNode ( 1 ) ; head -> next = newNode ( 2 ) ; head -> next -> next = newNode ( 3 ) ; head -> next -> next -> next = newNode ( 4 ) ; head -> next -> next -> next -> next = newNode ( 5 ) ; cout << " Given ▁ Linked ▁ List STRNEWLINE " ; printlist ( head ) ; head = rearrangeEvenOdd ( head ) ; cout << " Modified ▁ Linked ▁ List STRNEWLINE " ; printlist ( head ) ; return 0 ; }