Segregate even and odd nodes of linked list

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
3. Set head as first even node as head of list.
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 */
void push(Node **headRef, int data){
	Node * newNode  = createNode(data);
	newNode->next = *headRef;
	*headRef  = newNode;
}
 
void printList(Node * head){
    while(head){
        printf("%d->" , head->data );
        head = head->next;
    }
 
    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){
 
    Node * current = head;
 
    //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
    current = head;
    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);
    		prev->next = current ; //notice current is already advanced.
    	}
    }
 
    //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 */
void push(Node **headRef, int data){
	Node * newNode  = createNode(data);
	newNode->next = *headRef;
	*headRef  = newNode;
}
 
void printList(Node * head){
    while(head){
        printf("%d->" , head->data );
        head = head->next;
    }
 
    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;
 
	Node *current  = head;
	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.