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

C++: Print matrix in counter-clockwise spiral form

We are given a matrix of any dimension and we need to print the matrix elements in counter clockwise direction.

	void counterClockspiralPrint(int R, int C, int mat[][MAX]) {
	int row = 0, col = 0;
	int m = R, n = C;
	while(row < m && col < n) {
	for(int i= row; i < m ; i++)
	cout<<mat[i][col]<<" ";
	col++;
	for(int i = col; i< n-1; i++)
	cout<<mat[m-1][i]<<" ";
	m--;
	for(int i = m; i >= row; i--)
	cout<<mat[i][n-1]<<" ";
	n--;
	for(int i = n-1; i >= col; i--)
	cout<<mat[row][i]<<" ";
	row++;
	}
	}
	int main()
	{
	int R = 3;
	int C = 4;
	int mat[][MAX] = {{ 1, 2, 3, 4 },
	{ 5, 6, 7, 8 },
	{ 9, 10, 11, 12 } };
	counterClockspiralPrint(R, C, mat);
	return 0;
	}

view raw mat_ac_spiral.cpp hosted with ❤ by GitHub

Output: 1 5 9 10 11 12 8 4 3 2 6 7

C++: Find all the unique elements in a matrix

We are given a matrix of any dimension and wee need to print all the elements that are unique i.e appearing only once. So here is the c++ code for the algorithm.

	#include <bits/stdc++.h>
	using namespace std;
	#define R 4
	#define C 4
	void uniqueElement(int mat[][MAX]){
	map<int, int> cnt;
	for(int i=0; i<R; i++){
	for(int j=0; j<C; j++) {
	cnt[mat[i][j]]++;
	}
	}
	cout<<"The unique elements in the matrix are "<<endl;
	for(auto i: cnt){
	if(i.second == 1)
	cout<<i.first<<" ";
	}
	}
	int main()
	{
	int mat[][MAX] = { {2, 1, 4, 3},
	{1, 2, 3, 2},
	{3, 6, 2, 3},
	{5, 2, 5, 9} };
	uniqueElement(mat);
	return 0;
	}

view raw unique_el_matrx.cpp hosted with ❤ by GitHub

Output:
The unique elements in the matrix are 4 6 9

Explanation:

First, in the 'main' function, we create the matrix 'mat' of size 4 with 16 elements. Then we call the function 'uniqueElement' with the matrix 'mat' as the parameter. Note, at the top of the program, we have defined R(row) as 4 and C(col) as 4.

In the function 'uniqueElement', we first declare a map 'cnt' of integer type. Then we loop through all the elements of the matrix and increment the frequency of all the elements using 'cnt[mat[i][j]++'. After the loop, all the elements in the matrix will be mapped to its corresponding frequency.

After this, we loop through the map 'cnt' and print the elements with frequency 1.

C++: Turn a matrix by 180 degree.

We are given a matrix of any dimension and we need to turn it by 180 degree. Here is the source code for the algorithm in c++.

	#include <bits/stdc++.h>
	using namespace std;
	#define R 3
	#define C 4
	void printMatrix(int mat[][S]);
	void turnOneEighty(int mat[R][C]) {
	int row = 0, m = R-1;
	while(row < m) {
	for(int i=0; i < C; i++)
	swap(mat[row][i], mat[m][C-1-i]);
	row++;
	m--;
	if(row == m) {
	int col = 0, n = C-1;
	while(col < n)
	swap(mat[row][col++], mat[row][n--]);
	}
	}
	cout<<"\n\nMatrix turned 180 degree "<<endl;
	printMatrix(mat);
	}
	int main() {
	int mat[R][C] = { {1, 2, 3, 4},
	{5, 6, 7, 8},
	{9, 10, 11, 12} };
	cout<<"\nOriginal matrix is "<<endl;
	printMatrix(mat);
	turnOneEighty(mat);
	return 0;
	}

view raw turn_one_eighty.cpp hosted with ❤ by GitHub

Output:  12  11  10  9
               8    7    6   5
               4    3    2    1
             

C++: Print a Matrix in Spiral Form

We are given a matrix of any dimension, say 3x3, 4x4 or 4x3, and we are required to print the elements of the matrix in spiral form.

	#include <bits/stdc++.h>
	using namespace std;
	#define R 3
	#define C 4
	void printMatrixSpiral(int m, int n, int mat[R][C]) {
	int row = 0, col = 0;
	while(row<m && col<n) {
	for(int i=col; i<n; i++) {
	cout<<mat[row][i]<<" ";
	}
	row++;
	for(int i = row; i<m; i++) {
	cout<<mat[i][n-1]<<" ";
	}
	n--;
	if(row<m) {
	for(int i=n-1; i>=col; i--){
	cout<<mat[m-1][i]<<" ";
	}
	}
	m--;
	if(col<n) {
	for(int i= m-1; i>=row; i--) {
	cout<<mat[i][col]<<" ";
	}
	}
	col++;
	}
	}
	int main() {
	int mat[R][C] = {{1, 2, 3, 4},
	{5, 6, 7,8},
	{9, 10, 11, 12}
	};
	printMatrixSpiral(R, C, mat);
	return 0;
	}

view raw matrix_spiral.cpp hosted with ❤ by GitHub

Output: 1 2 3 4 8 12 11 10 9 5 6 7

C++: Rotate Matrix to the right.

Given a square matrix and we need to write a program to rotate the matrix to the right. Here is the code for the program.

	#include <bits/stdc++.h>
	using namespace std;
	#define R 4
	#define C 4
	void rotateMatrix(int m, int n, int mat[R][C]) {
	int row = 0, col =0;
	int curr, prev;
	while(row<m && col<n) {
	if(row+1 == m || col+1 == n)
	break;
	prev = mat[row+1][col];
	for(int i= col; i<n; i++) {
	curr = mat[row][i];
	mat[row][i] = prev;
	prev = curr;
	}
	row++;
	for(int i=row; i<m; i++) {
	curr = mat[i][n-1];
	mat[i][n-1] = prev;
	prev = curr;
	}
	n--;
	if(row<m) {
	for(int i= n-1; i>=col; i--) {
	curr = mat[m-1][i];
	mat[m-1][i] = prev;
	prev = curr;
	}
	}
	m--;
	if(col<n){
	for(int i=m-1; i>=row; i--) {
	curr = mat[i][col];
	mat[i][col] = prev;
	prev = curr;
	}
	}
	col++;
	}
	for(int i=0; i<R; i++) {
	for(int j=0; j<C; j++)
	cout<<mat[i][j]<<" ";
	cout<<endl;
	}
	}
	int main() {
	int mat[R][C] = {{1,2,3,4}, {5,6,7,8}, {9,10,11,12}, {13,14,15,16}};
	rotateMatrix(R,C,mat);
	return 0;
	}

view raw rotate_mat_r.cpp hosted with ❤ by GitHub

Output:
5    1    2    3
9    10   6    4
13   11   7    8
14   15   16   12