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

C++: Remove all the duplicates from a sorted linked list.

In this C++ tutorial, we will learn how to remove all the duplicate entries from a sorted linked list. Here 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<<endl;
	node = node->next;
	}
	}
	void removeDuplicate(Node* head) {
	Node* after;
	if(head == NULL)
	return;
	while(head->next != NULL) {
	if(head->data == head->next->data){
	after = head->next->next;
	delete head->next;
	head->next = after;
	continue;
	}
	head = head->next;
	}
	}
	int main() {
	Node *head = NULL;
	push(&head, 1);
	push(&head, 2);
	push(&head, 3);
	push(&head, 3);
	push(&head, 4);
	push(&head, 5);
	push(&head, 5);
	push(&head, 5);
	push(&head, 5);
	push(&head, 5);
	push(&head, 5);
	push(&head, 5);
	push(&head, 6);
	push(&head, 6);
	push(&head, 7);
	push(&head, 8);
	push(&head, 8);
	push(&head, 9);
	printList(head);
	cout<<endl;
	removeDuplicate(head);
	printList(head);
	return 0;
	}

view raw remove_dup_sort_linked_list.cpp hosted with ❤ by GitHub

Output: 9 8 8 8 7 6 6 5 5 5 5 5 5 5 4 3 3 2 1
             After removing the duplicates -
             9 8 7 6 5 4 3 2 1