In this article, we are going to learn how to rearrange the nodes in a singly linked list so that its odd elements come before its even elements.
The basic idea is to split the list into two separate lists for even elements and odd elements, and then to append the even elements to the odd elements.
The time complexity of this algorithm is O(N) where N is the number of nodes in the input linked list.
#include <iostream>#include "Node.h"using namespace std;//Rearrange a linked list such that all the odd elements come before the even elementsNode * rearrange(Node * head){Node *current = head;Node *prevOdd = nullptr, *prevEven = nullptr;Node *evenHead = nullptr, *oddHead = nullptr;while(current){// add current in odd elements listif(current->data % 2 == 1){if(prevOdd)prevOdd->next = current;elseoddHead = current;prevOdd = current;}else {if(prevEven)prevEven->next = current;elseevenHead = current;prevEven = current;}current = current->next;}//prevEven->next may be nullptr or an odd node.if(evenHead)prevEven->next = nullptr;//append even elements to odd elementsif(oddHead)prevOdd->next = evenHead;elseoddHead = evenHead;return oddHead;}//arr will be used for list1 valuesint arr[] = { 1,2,4,3,5,7,8,6,9};int size = 9;
In main.cpp, we do the following:
current is the current node. prevOdd. Since current has an odd value, current is appended to the odd list and prevOdd is updated to point to current.prevEven. Since current has an even value, current is appended to the even list and prevEven is updated to point tocurrent.prevEven. We also see that prevEven->next may be nullptr or an odd node. It is updated to NULL to prevent loops.oddHead or evenHead may point to empty lists.