# Segregate even and odd nodes of linked list

In previous post: Split linked list into two containing alternate nodes, we saw how to split two list and use last pointer reference. In this post, we will   learn to segregate even and odd nodes of linked list. There should not be any new memory allocated and only movement of nodes is allowed. Example of problem is given below:

```Original list: 1->2->3->4->5->6->NULL
Even list: 2->4->6->NULL
Odd list: 1->3->5->NULL```

One way to segregate even odd nodes is to move all odd nodes to either start or end of the original list and then split the linked list. Drawback of moving odd nodes at start is that we may lose order of nodes in original list. Moving to end will require one extra traversal of list and special handling of last node to preserve order of list.

## Algorithm to segregate even and odd nodes of list

```1. Find the end of list, call it initialEnd
2. Till first even node is found,
2.a move odd nodes to end
4. Scan through remaining nodes of list
4.a If node is odd, move to end
4.b If node is even, skip it
Since this loop will work till initialEnd node, this node will not be processed in loop.
5. Save next of initialEnd, it will head of odd list
5. Special case of end node, if node is even, skip it.
If node is odd, move to end.```

### Segregate even and odd nodes implementation

```#include<stdlib.h>
#include<stdio.h>

typedef struct node{
int data;
struct node *next;
} Node;

Node * createNode(int val){
Node * newNode = (Node *)malloc(sizeof(Node));
if(newNode){
newNode->data = val;
newNode->next = NULL;
}
return newNode;
}

/* This function inserts node at the head of linked list */
Node * newNode  = createNode(data);
}

}

printf("NULL");
printf("\n");
}

/* Function to insert a node at the beginning of the linked list */
void moveNodeEnd(Node** lastPtrRef, Node **sourceRef)
{
/* New node is allocated */
Node * newNode = *sourceRef;

*sourceRef = newNode->next;

newNode->next = NULL;
/* link the old list off the new node */
*lastPtrRef = newNode;
}

void splitEvenOddNodes(Node *head, Node **evenList,Node **oddList){

//Find the tail of list
while(current && current->next){
current = current->next;
}

Node *initialEnd = current;
Node **lastPtrRefOdd = &(initialEnd->next);

//Move all nodes before first even node to end
while(current && current->data%2 != 0){
moveNodeEnd(lastPtrRefOdd, &current);
lastPtrRefOdd = &((*lastPtrRefOdd)->next);
}

Node * prev;
while(current && current != initialEnd){
//Even node
if(current->data%2 == 0){
//first even node
if(*evenList == NULL){
*evenList = current;
}
prev = current;
current = current->next;
}
else{
//Odd node
moveNodeEnd(lastPtrRefOdd, &current);
lastPtrRefOdd = &((*lastPtrRefOdd)->next);
}
}

//Save the next node, it will be start of odd list
*oddList = initialEnd->next;
initialEnd->next = NULL;

if(initialEnd->data%2 != 0){
moveNodeEnd(lastPtrRefOdd, &initialEnd);
lastPtrRefOdd = &((*lastPtrRefOdd)->next);
}
}

/* Driver program to run above code */
int main(){
Node * L1 = NULL;

push(&L1,12);
push(&L1,10);
push(&L1,1);
push(&L1,6);
push(&L1,5);
push(&L1,2);

printList(L1);

Node *a = NULL;
Node *b = NULL;

splitEvenOddNodes(L1, &a,&b);

printList(a);
printList(b);

return 0;
}
```

There is another very similar solution to what is done in splitting list into two with alternate nodes. Only change will be the condition to put node into appropriate list. Below is the code.

```#include<stdlib.h>
#include<stdio.h>

typedef struct node{
int data;
struct node *next;
} Node;

Node * createNode(int val){
Node * newNode = (Node *)malloc(sizeof(Node));
if(newNode){
newNode->data = val;
newNode->next = NULL;
}
return newNode;
}
/* This function inserts node at the head of linked list */
Node * newNode  = createNode(data);
}

}

printf("NULL");
printf("\n");
}

/* Function to insert a node at the beginning of the linked list */
void moveNodeEnd(Node** lastPtrRef, Node **sourceRef)
{
/* New node is allocated */
Node * newNode = *sourceRef;

*sourceRef = newNode->next;

newNode->next = NULL;
/* link the old list off the new node */
*lastPtrRef = newNode;
}

void splitEvenOddNodes(Node *head, Node **evenList,Node **oddList){
//create start of list a;
Node *a = NULL;
//create start of list a;
Node *b = NULL;

Node **lastPtrRefEven = &a;
Node **lastPtrRefOdd = &b;

while(current){
//even node
if(current->data%2 == 0){
//Moving current node to even list
moveNodeEnd(lastPtrRefEven, &current);
lastPtrRefEven = &((*lastPtrRefEven)->next);
}
//Odd node
else{
//Moving current node to odd list
moveNodeEnd(lastPtrRefOdd,&current);
lastPtrRefOdd = &((*lastPtrRefOdd)->next);
}
}
*evenList = a;
*oddList = b;
}

/* Driver program to run above code */
int main(){
Node * L1 = NULL;

push(&L1,12);
push(&L1,10);
push(&L1,8);
push(&L1,6);
push(&L1,4);
push(&L1,2);

printList(L1);

Node *a = NULL;
Node *b = NULL;

splitEvenOddNodes(L1, &a,&b);

printList(a);
printList(b);

return 0;
}
```

Output

```Original list: 2->5->6->1->10->12->NULL
Even list: 2->6->10->12->NULL
Odd list: 5->1->NULL```

Complexity of code to segregate even and odd nodes is O(n) as entire list needs to be traversed once. There O(1) space complexity as no new node is being allocated and only nodes are moved.

Please share your views and suggestions. We would love to hear what you have to say. Sharing is caring.