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.

main.cpp

Node.h

#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:

- Lines 11–28: We traverse a list where
`current`

is the current node. - Lines 13–18: We point to the last added odd node with
`prevOdd`

. Since`current`

has an odd value,`current`

is appended to the odd list and`prevOdd`

is updated to point to`current`

. - Lines 21–25: We point to the last added even node with
`prevEven`

. Since`current`

has an even value,`current`

is appended to the even list and`prevEven`

is updated to point to`current`

. - Lines 30–31: We point to the last even node with
`prevEven`

. We also see that`prevEven->next`

may be`nullptr`

or an odd node. It is updated to`NULL`

to prevent loops. - Lines 34–37: We append even elements to odd elements where
`oddHead`

or`evenHead`

may point to empty lists.

TRENDING TOPICS