C++: Segregate even and odd nodes in a linked list.

In this C++ tutorial, we will learn how to segregate even and odd nodes in a linked list.

We are given a singly linked list with even and odd nodes at random positions. What we need to do is segregate even and odd nodes such that all the even nodes comes first and then the odd nodes. Below is the code for the algorithm in C++.

	#include<bits/stdc++.h>
	using namespace std;
	class Node {
	public:
	int data;
	Node* next;
	};
	void push(Node **head_ref, int new_data) {
	Node *new_node = new Node();
	new_node->data = new_data;
	new_node->next = *head_ref;
	*head_ref = new_node;
	}
	void printList(Node* node) {
	while(node != NULL) {
	cout<<node->data<<" ";
	node = node->next;
	}
	}
	Node *getTail(Node *cur) {
	while(cur != NULL && cur->next != NULL) {
	cur = cur->next;
	}
	return cur;
	}
	void segregateList(Node **headRef) {
	Node *cur = *headRef;
	Node *tail = getTail(*headRef);
	Node *endNode = tail;
	Node *newHead = NULL;
	Node *prev = NULL;
	while(cur != endNode) {
	if(cur->data %2 != 0) {
	if(prev)
	prev->next = cur->next;
	Node *temp = cur->next;
	cur->next = NULL;
	tail->next = cur;
	tail = cur;
	cur = temp;
	}
	else {
	if(newHead == NULL)
	newHead = cur;
	prev = cur;
	cur = cur->next;
	}
	}
	*headRef = newHead;
	}
	int main() {
	Node *a = NULL;
	push(&a, 6);
	push(&a, 7);
	push(&a, 1);
	push(&a, 4);
	push(&a, 5);
	push(&a, 10);
	push(&a, 12);
	push(&a, 8);
	push(&a, 15);
	push(&a, 17);
	cout<<"Before segregation - ";
	printList(a);
	cout<<endl;
	cout<<"After segregation- ";
	segregateList(&a);
	printList(a);
	return 0;
	}

view raw even_odd_ll.cpp hosted with ❤ by GitHub

Output:

Before segregation- 17 15 8 12 10 5 4 1 7 6

After segregation- 8 12 10 4 6 17 15 5 1 7