Skip to main content

Sum of all odd frequency nodes of the linked list

Given a linked list, Which is contains integer values. Our goal is to sum all the nodes which is occur odd number of times. For example.

Example 1
---------
Linked List :  2  5  4  2  2 4
//Odd occurrences
[2] occurring 3 times
[5] occurring 1 times
Result : (2*3)+ (5*1)  = 11


Example 2
---------
Linked List :  1  4  11  4  4  1 11
//Odd occurrences
[4] occurring 3 times
Result : (4*3) = 12


Example 3
---------
Linked List :   5  5 
//Odd occurrences
None
Result      :   0

Before solving this problem note that linked list element can be in unsorted form. In Given below approach are first combine group of similar Elements. After that count odd elements occurrence. Here given code implementation process.

// C Program
// Sum of all odd frequency nodes of the linked list
#include <stdio.h>
 //For malloc function
#include <stdlib.h>

//Linked List Node
struct Node
{
	int data;
	struct Node *next;
};
//Create a node of linked list
struct Node *create_node(int data)
{
	//Create dynamic node
	struct Node *node = (struct Node *) malloc(sizeof(struct Node));
	if (node == NULL)
	{
		printf("Memory overflow\n");
	}
	else
	{
		//Set initial node value
		node->data = data;
		node->next = NULL;
	}
	return node;
}
//Add new node at end of linked list 
void insert(struct Node **head, int data)
{
	struct Node *node = create_node(data);
	if ( *head == NULL)
	{
		*head = node;
	}
	else
	{
		struct Node *temp = *head;
		//Find last node
		while (temp->next != NULL)
		{
			temp = temp->next;
		}
		//Add node at last possition
		temp->next = node;
	}
}
//Display linked list element
void display(struct Node *head)
{
	if (head == NULL)
	{
		printf("\nEmpty linked list\n");
		return;
	}
	struct Node *temp = head;
	printf("\n Linked List : ");
	while (temp != NULL)
	{
		printf("  %d", temp->data);
		//visit to next node
		temp = temp->next;
	}
	printf("\n");
}
// This function are takes O(N^2) time to combine similar elements
void group_element(struct Node *head)
{
	//Define some auxiliary variables
	struct Node *outer = head;
	struct Node *inner = NULL;
	struct Node *auxiliary = NULL;
	int temp = 0;
	while (outer != NULL)
	{
		auxiliary = outer->next;
		inner = auxiliary;
		while (inner != NULL && auxiliary != NULL)
		{
			if (auxiliary->data == outer->data)
			{
				//visit to next node
				auxiliary = auxiliary->next;
				if (auxiliary != NULL)
				{
					inner = auxiliary->next;
				}
				else
				{
					inner = auxiliary;
				}
			}
			else if (outer->data == inner->data)
			{
				//Swap node value
				temp = auxiliary->data;
				auxiliary->data = inner->data;
				inner->data = temp;
				//visit to next upcomming nodes
				auxiliary = auxiliary->next;
				inner = inner->next;
			}
			else
			{
				inner = inner->next;
			}
		}
		outer = auxiliary;
	}
}
//Sum the all elements which are occurs in odd number of team
void sum_odd_frequency_nodes(struct Node *head)
{
	if (head == NULL)
	{
		//When linked list is empty
		return;
	}
	//Grouping of similar nodes elements
	group_element(head);
	//Use to iterating linked list nodes
	struct Node *outer = head;
	struct Node *inner = NULL;
	//Define resultant variables
	int counter = 0;
	int result = 0;
	// This loop takes O(N) time to find the frequency of all nodes
	while (outer != NULL)
	{
		//Set node counter
		counter = 1;
		//start to next node
		inner = outer->next;
		//Count repeated nodes
		while (inner != NULL && inner->data == outer->data)
		{
			counter++;
			inner = inner->next;
		}
		if ((counter % 2) != 0)
		{
			if (outer != head)
			{
				printf(" +");
			}
			printf(" (%dx%d)", outer->data, counter);
			//When odd frequency node get
			result += (outer->data) *counter;
		}
		//Get next frequency node in list
		outer = inner;
	}
	printf("\n Odd frequency node sum is : %d\n", result);
}
int main()
{
	struct Node *head = NULL;
	//Create linked list
	insert( &head, 4);
	insert( &head, 7);
	insert( &head, 2);
	insert( &head, 3);
	insert( &head, 4);
	insert( &head, 3);
	insert( &head, 4);
	insert( &head, 3);
	insert( &head, 2);
	insert( &head, 4);
	insert( &head, 4);
	//Display of linked list nodes
	display(head);
	sum_odd_frequency_nodes(head);
	return 0;
}

Output

 Linked List :   4  7  2  3  4  3  4  3  2  4  4
 (4x5) + (3x3) + (7x1)
 Odd frequency node sum is : 36
// Java Program
// Sum of all odd frequency nodes of the linked list

//Node of LinkedList
class Node
{
	public int data;
	public Node next;
	public Node(int data)
	{
		//Set node value
		this.data = data;
		this.next = null;
	}
}
public class MyLinkedList
{
	public Node head;
	public Node tail;
	//Class constructors
	public MyLinkedList()
	{
		this.head = null;
		this.tail = null;
	}
	//insert node at last of linke list
	public void insert(int data)
	{
		//Create a node
		Node node = new Node(data);
		if (this.head == null)
		{
			//When linked list empty add first node
			this.head = node;
			this.tail = node;
		}
		else
		{
			//Add new node at end of linked list
			this.tail.next = node;
			this.tail = node;
		}
	}
	//Display linked list element
	public void display()
	{
		if (this.head == null)
		{
			System.out.print("\nEmpty linked list\n");
			return;
		}
		Node temp = this.head;
		System.out.print("\n Linked List : ");
		while (temp != null)
		{
			System.out.print("  " + temp.data);
			temp = temp.next;
		}
		System.out.print("\n");
	}
	// This function are takes O(N^2) time to combine similar elements
	public void group_element()
	{
		//Define some auxiliary variables
		Node outer = this.head;
		Node inner = null;
		Node auxiliary = null;
		int temp = 0;
		while (outer != null)
		{
			auxiliary = outer.next;
			inner = auxiliary;
			while (inner != null && auxiliary != null)
			{
				if (auxiliary.data == outer.data)
				{
					//visit to next node
					auxiliary = auxiliary.next;
					if (auxiliary != null)
					{
						inner = auxiliary.next;
					}
					else
					{
						inner = auxiliary;
					}
				}
				else if (outer.data == inner.data)
				{
					//Swap node value
					temp = auxiliary.data;
					auxiliary.data = inner.data;
					inner.data = temp;
					//visit to next upcomming nodes
					auxiliary = auxiliary.next;
					inner = inner.next;
				}
				else
				{
					inner = inner.next;
				}
			}
			outer = auxiliary;
		}
	}
	//Sum the all elements which are occurs in odd number of team
	public void sum_odd_frequency_nodes()
	{
		if (this.head == null)
		{
			//When linked list is empty
			return;
		}
		//Grouping of similar nodes elements
		this.group_element();
		//Use to iterating linked list nodes
		Node outer = this.head;
		Node inner = null;
		//Define resultant variables
		int counter = 0;
		int result = 0;
		// This loop takes O(N) time to find the frequency of all nodes
		while (outer != null)
		{
			//Set node counter
			counter = 1;
			//start to next node
			inner = outer.next;
			//Count repeated nodes
			while (inner != null && inner.data == outer.data)
			{
				counter++;
				inner = inner.next;
			}
			if ((counter % 2) != 0)
			{
				if (outer != head)
				{
					System.out.print(" +");
				}
				System.out.print(" (" + outer.data + "x" + counter + ")");
				//When odd frequency node get
				result += (outer.data) * counter;
			}
			//Get next frequency node in list
			outer = inner;
		}
		System.out.print("\n Odd frequency node sum is : " + result + "\n");
	}
	public static void main(String[] args)
	{
		MyLinkedList obj = new MyLinkedList();
		//Create linked list
		obj.insert(4);
		obj.insert(7);
		obj.insert(2);
		obj.insert(3);
		obj.insert(4);
		obj.insert(3);
		obj.insert(4);
		obj.insert(3);
		obj.insert(2);
		obj.insert(4);
		obj.insert(4);
		//Display of linked list nodes
		obj.display();
		obj.sum_odd_frequency_nodes();
	}
}

Output

 Linked List :   4  7  2  3  4  3  4  3  2  4  4
 (4x5) + (3x3) + (7x1)
 Odd frequency node sum is : 36
//Include header file
#include <iostream>

using namespace std;
// C++ Program
// Sum of all odd frequency nodes of the linked list

//Node of LinkedList
class Node
{
	public: int data;
	Node * next;
	Node(int data)
	{
		//Set node value
		this->data = data;
		this->next = NULL;
	}
};
class MyLinkedList
{
	public: Node * head;
	Node * tail;
	//Class constructors
	MyLinkedList()
	{
		this->head = NULL;
		this->tail = NULL;
	}
	//insert node at last of linke list
	void insert(int data)
	{
		//Create a node
		Node * node = new Node(data);
		if (this->head == NULL)
		{
			//When linked list empty add first node
			this->head = node;
			this->tail = node;
		}
		else
		{
			//Add new node at end of linked list
			this->tail->next = node;
			this->tail = node;
		}
	}
	//Display linked list element
	void display()
	{
		if (this->head == NULL)
		{
			cout << "\nEmpty linked list\n";
			return;
		}
		Node * temp = this->head;
		cout << "\n Linked List : ";
		while (temp != NULL)
		{
			cout << "  " << temp->data;
			temp = temp->next;
		}
		cout << "\n";
	}
	// This function are takes O(N^2) time to combine similar elements
	void group_element()
	{
		//Define some auxiliary variables
		Node * outer = this->head;
		Node * inner = NULL;
		Node * auxiliary = NULL;
		int temp = 0;
		while (outer != NULL)
		{
			auxiliary = outer->next;
			inner = auxiliary;
			while (inner != NULL && auxiliary != NULL)
			{
				if (auxiliary->data == outer->data)
				{
					//visit to next node
					auxiliary = auxiliary->next;
					if (auxiliary != NULL)
					{
						inner = auxiliary->next;
					}
					else
					{
						inner = auxiliary;
					}
				}
				else if (outer->data == inner->data)
				{
					//Swap node value
					temp = auxiliary->data;
					auxiliary->data = inner->data;
					inner->data = temp;
					//visit to next upcomming nodes
					auxiliary = auxiliary->next;
					inner = inner->next;
				}
				else
				{
					inner = inner->next;
				}
			}
			outer = auxiliary;
		}
	}
	//Sum the all elements which are occurs in odd number of team
	void sum_odd_frequency_nodes()
	{
		if (this->head == NULL)
		{
			//When linked list is empty
			return;
		}
		//Grouping of similar nodes elements
		this->group_element();
		//Use to iterating linked list nodes
		Node * outer = this->head;
		Node * inner = NULL;
		//Define resultant variables
		int counter = 0;
		int result = 0;
		// This loop takes O(N) time to find the frequency of all nodes
		while (outer != NULL)
		{
			//Set node counter
			counter = 1;
			//start to next node
			inner = outer->next;
			//Count repeated nodes
			while (inner != NULL && inner->data == outer->data)
			{
				counter++;
				inner = inner->next;
			}
			if ((counter % 2) != 0)
			{
				if (outer != this->head)
				{
					cout << " +";
				}
				cout << " (" << outer->data << "x" << counter << ")";
				//When odd frequency node get
				result += (outer->data) * counter;
			}
			//Get next frequency node in list
			outer = inner;
		}
		cout << "\n Odd frequency node sum is : " << result << "\n";
	}
};
int main()
{
	MyLinkedList obj = MyLinkedList();
	//Create linked list
	obj.insert(4);
	obj.insert(7);
	obj.insert(2);
	obj.insert(3);
	obj.insert(4);
	obj.insert(3);
	obj.insert(4);
	obj.insert(3);
	obj.insert(2);
	obj.insert(4);
	obj.insert(4);
	//Display of linked list nodes
	obj.display();
	obj.sum_odd_frequency_nodes();
	return 0;
}

Output

 Linked List :   4  7  2  3  4  3  4  3  2  4  4
 (4x5) + (3x3) + (7x1)
 Odd frequency node sum is : 36
//Include namespace system
using System;

// C# Program
// Sum of all odd frequency nodes of the linked list

//Node of LinkedList
class Node
{
	public int data;
	public Node next;
	public Node(int data)
	{
		//Set node value
		this.data = data;
		this.next = null;
	}
}
class MyLinkedList
{
	public Node head;
	public Node tail;
	//Class constructors
	public MyLinkedList()
	{
		this.head = null;
		this.tail = null;
	}
	//insert node at last of linke list
	public void insert(int data)
	{
		//Create a node
		Node node = new Node(data);
		if (this.head == null)
		{
			//When linked list empty add first node
			this.head = node;
			this.tail = node;
		}
		else
		{
			//Add new node at end of linked list
			this.tail.next = node;
			this.tail = node;
		}
	}
	//Display linked list element
	public void display()
	{
		if (this.head == null)
		{
			Console.Write("\nEmpty linked list\n");
			return;
		}
		Node temp = this.head;
		Console.Write("\n Linked List : ");
		while (temp != null)
		{
			Console.Write("  " + temp.data);
			temp = temp.next;
		}
		Console.Write("\n");
	}
	// This function are takes O(N^2) time to combine similar elements
	public void group_element()
	{
		//Define some auxiliary variables
		Node outer = this.head;
		Node inner = null;
		Node auxiliary = null;
		int temp = 0;
		while (outer != null)
		{
			auxiliary = outer.next;
			inner = auxiliary;
			while (inner != null && auxiliary != null)
			{
				if (auxiliary.data == outer.data)
				{
					//visit to next node
					auxiliary = auxiliary.next;
					if (auxiliary != null)
					{
						inner = auxiliary.next;
					}
					else
					{
						inner = auxiliary;
					}
				}
				else if (outer.data == inner.data)
				{
					//Swap node value
					temp = auxiliary.data;
					auxiliary.data = inner.data;
					inner.data = temp;
					//visit to next upcomming nodes
					auxiliary = auxiliary.next;
					inner = inner.next;
				}
				else
				{
					inner = inner.next;
				}
			}
			outer = auxiliary;
		}
	}
	//Sum the all elements which are occurs in odd number of team
	public void sum_odd_frequency_nodes()
	{
		if (this.head == null)
		{
			//When linked list is empty
			return;
		}
		//Grouping of similar nodes elements
		this.group_element();
		//Use to iterating linked list nodes
		Node outer = this.head;
		Node inner = null;
		//Define resultant variables
		int counter = 0;
		int result = 0;
		// This loop takes O(N) time to find the frequency of all nodes
		while (outer != null)
		{
			//Set node counter
			counter = 1;
			//start to next node
			inner = outer.next;
			//Count repeated nodes
			while (inner != null && inner.data == outer.data)
			{
				counter++;
				inner = inner.next;
			}
			if ((counter % 2) != 0)
			{
				if (outer != head)
				{
					Console.Write(" +");
				}
				Console.Write(" (" + outer.data + "x" + counter + ")");
				//When odd frequency node get
				result += (outer.data) * counter;
			}
			//Get next frequency node in list
			outer = inner;
		}
		Console.Write("\n Odd frequency node sum is : " + result + "\n");
	}
	public static void Main(String[] args)
	{
		MyLinkedList obj = new MyLinkedList();
		//Create linked list
		obj.insert(4);
		obj.insert(7);
		obj.insert(2);
		obj.insert(3);
		obj.insert(4);
		obj.insert(3);
		obj.insert(4);
		obj.insert(3);
		obj.insert(2);
		obj.insert(4);
		obj.insert(4);
		//Display of linked list nodes
		obj.display();
		obj.sum_odd_frequency_nodes();
	}
}

Output

 Linked List :   4  7  2  3  4  3  4  3  2  4  4
 (4x5) + (3x3) + (7x1)
 Odd frequency node sum is : 36
<?php
// Php Program
// Sum of all odd frequency nodes of the linked list

//Node of LinkedList
class Node
{
	public $data;
	public $next;

	function __construct($data)
	{
		//Set node value
		$this->data = $data;
		$this->next = null;
	}
}
class MyLinkedList
{
	public $head;
	public $tail;
	//Class constructors
	function __construct()
	{
		$this->head = null;
		$this->tail = null;
	}
	//insert node at last of linke list
	public	function insert($data)
	{
		//Create a node
		$node = new Node($data);
		if ($this->head == null)
		{
			//When linked list empty add first node
			$this->head = $node;
			$this->tail = $node;
		}
		else
		{
			//Add new node at end of linked list
			$this->tail->next = $node;
			$this->tail = $node;
		}
	}
	//Display linked list element
	public	function display()
	{
		if ($this->head == null)
		{
			echo "\nEmpty linked list\n";
			return;
		}
		$temp = $this->head;
		echo "\n Linked List : ";
		while ($temp != null)
		{
			echo "  ". $temp->data;
			$temp = $temp->next;
		}
		echo "\n";
	}
	// This function are takes O(N^2) time to combine similar elements
	public	function group_element()
	{
		//Define some auxiliary variables
		$outer = $this->head;
		$inner = null;
		$auxiliary = null;
		$temp = 0;
		while ($outer != null)
		{
			$auxiliary = $outer->next;
			$inner = $auxiliary;
			while ($inner != null && $auxiliary != null)
			{
				if ($auxiliary->data == $outer->data)
				{
					//visit to next node
					$auxiliary = $auxiliary->next;
					if ($auxiliary != null)
					{
						$inner = $auxiliary->next;
					}
					else
					{
						$inner = $auxiliary;
					}
				}
				else if ($outer->data == $inner->data)
				{
					//Swap node value
					$temp = $auxiliary->data;
					$auxiliary->data = $inner->data;
					$inner->data = $temp;
					//visit to next upcomming nodes
					$auxiliary = $auxiliary->next;
					$inner = $inner->next;
				}
				else
				{
					$inner = $inner->next;
				}
			}
			$outer = $auxiliary;
		}
	}
	//Sum the all elements which are occurs in odd number of team
	public	function sum_odd_frequency_nodes()
	{
		if ($this->head == null)
		{
			//When linked list is empty
			return;
		}
		//Grouping of similar nodes elements
		$this->group_element();
		//Use to iterating linked list nodes
		$outer = $this->head;
		$inner = null;
		//Define resultant variables
		$counter = 0;
		$result = 0;
		// This loop takes O(N) time to find the frequency of all nodes
		while ($outer != null)
		{
			//Set node counter
			$counter = 1;
			//start to next node
			$inner = $outer->next;
			//Count repeated nodes
			while ($inner != null && $inner->data == $outer->data)
			{
				$counter++;
				$inner = $inner->next;
			}
			if (($counter % 2) != 0)
			{
				if ($outer != $this->head)
				{
					echo "+";
				}
				echo " (". $outer->data ."x". $counter .")";
				//When odd frequency node get
				$result += ($outer->data) * $counter;
			}
			//Get next frequency node in list
			$outer = $inner;
		}
		echo "\n Odd frequency node sum is : ". $result ."\n";
	}
}

function main()
{
	$obj = new MyLinkedList();
	//Create linked list
	$obj->insert(4);
	$obj->insert(7);
	$obj->insert(2);
	$obj->insert(3);
	$obj->insert(4);
	$obj->insert(3);
	$obj->insert(4);
	$obj->insert(3);
	$obj->insert(2);
	$obj->insert(4);
	$obj->insert(4);
	//Display of linked list nodes
	$obj->display();
	$obj->sum_odd_frequency_nodes();
}
main();

Output

 Linked List :   4  7  2  3  4  3  4  3  2  4  4
 (4x5)+ (3x3)+ (7x1)
 Odd frequency node sum is : 36
// Node Js Program
// Sum of all odd frequency nodes of the linked list

//Node of LinkedList
class Node
{
	constructor(data)
	{
		//Set node value
		this.data = data;
		this.next = null;
	}
}
class MyLinkedList
{
	//Class constructors
	constructor()
	{
		this.head = null;
		this.tail = null;
	}
	//insert node at last of linke list
	insert(data)
	{
		//Create a node
		var node = new Node(data);
		if (this.head == null)
		{
			//When linked list empty add first node
			this.head = node;
			this.tail = node;
		}
		else
		{
			//Add new node at end of linked list
			this.tail.next = node;
			this.tail = node;
		}
	}
	//Display linked list element
	display()
	{
		if (this.head == null)
		{
			process.stdout.write("\nEmpty linked list\n");
			return;
		}
		var temp = this.head;
		process.stdout.write("\n Linked List : ");
		while (temp != null)
		{
			process.stdout.write("  " + temp.data);
			temp = temp.next;
		}
		process.stdout.write("\n");
	}
	// This function are takes O(N^2) time to combine similar elements
	group_element()
	{
		//Define some auxiliary variables
		var outer = this.head;
		var inner = null;
		var auxiliary = null;
		var temp = 0;
		while (outer != null)
		{
			auxiliary = outer.next;
			inner = auxiliary;
			while (inner != null && auxiliary != null)
			{
				if (auxiliary.data == outer.data)
				{
					//visit to next node
					auxiliary = auxiliary.next;
					if (auxiliary != null)
					{
						inner = auxiliary.next;
					}
					else
					{
						inner = auxiliary;
					}
				}
				else if (outer.data == inner.data)
				{
					//Swap node value
					temp = auxiliary.data;
					auxiliary.data = inner.data;
					inner.data = temp;
					//visit to next upcomming nodes
					auxiliary = auxiliary.next;
					inner = inner.next;
				}
				else
				{
					inner = inner.next;
				}
			}
			outer = auxiliary;
		}
	}
	//Sum the all elements which are occurs in odd number of team
	sum_odd_frequency_nodes()
	{
		if (this.head == null)
		{
			//When linked list is empty
			return;
		}
		//Grouping of similar nodes elements
		this.group_element();
		//Use to iterating linked list nodes
		var outer = this.head;
		var inner = null;
		//Define resultant variables
		var counter = 0;
		var result = 0;
		// This loop takes O(N) time to find the frequency of all nodes
		while (outer != null)
		{
			//Set node counter
			counter = 1;
			//start to next node
			inner = outer.next;
			//Count repeated nodes
			while (inner != null && inner.data == outer.data)
			{
				counter++;
				inner = inner.next;
			}
			if ((counter % 2) != 0)
			{
				if (outer != this.head)
				{
					process.stdout.write(" +");
				}
				process.stdout.write(" (" + outer.data + "x" + counter + ")");
				//When odd frequency node get
				result += (outer.data) * counter;
			}
			//Get next frequency node in list
			outer = inner;
		}
		process.stdout.write("\n Odd frequency node sum is : " + result + "\n");
	}
}

function main()
{
	var obj = new MyLinkedList();
	//Create linked list
	obj.insert(4);
	obj.insert(7);
	obj.insert(2);
	obj.insert(3);
	obj.insert(4);
	obj.insert(3);
	obj.insert(4);
	obj.insert(3);
	obj.insert(2);
	obj.insert(4);
	obj.insert(4);
	//Display of linked list nodes
	obj.display();
	obj.sum_odd_frequency_nodes();
}
main();

Output

 Linked List :   4  7  2  3  4  3  4  3  2  4  4
 (4x5) + (3x3) + (7x1)
 Odd frequency node sum is : 36
#  Python 3 Program
#  Sum of all odd frequency nodes of the linked list

# Node of LinkedList
class Node :
	
	def __init__(self, data) :
		# Set node value
		self.data = data
		self.next = None
	

class MyLinkedList :
	
	# Class constructors
	def __init__(self) :
		self.head = None
		self.tail = None
	
	# insert node at last of linke list
	def insert(self, data) :
		# Create a node
		node = Node(data)
		if (self.head == None) :
			# When linked list empty add first node
			self.head = node
			self.tail = node
		else :
			# Add new node at end of linked list
			self.tail.next = node
			self.tail = node
		
	
	# Display linked list element
	def display(self) :
		if (self.head == None) :
			print("\nEmpty linked list\n", end = "")
			return
		
		temp = self.head
		print("\n Linked List : ", end = "")
		while (temp != None) :
			print("  ", temp.data, end = "")
			temp = temp.next
		
		print("\n", end = "")
	
	#  This function are takes O(N^2) time to combine similar elements
	def group_element(self) :
		# Define some auxiliary variables
		outer = self.head
		inner = None
		auxiliary = None
		temp = 0
		while (outer != None) :
			auxiliary = outer.next
			inner = auxiliary
			while (inner != None and auxiliary != None) :
				if (auxiliary.data == outer.data) :
					# visit to next node
					auxiliary = auxiliary.next
					if (auxiliary != None) :
						inner = auxiliary.next
					else :
						inner = auxiliary
					
				
				elif(outer.data == inner.data) :
					# Swap node value
					temp = auxiliary.data
					auxiliary.data = inner.data
					inner.data = temp
					# visit to next upcomming nodes
					auxiliary = auxiliary.next
					inner = inner.next
				else :
					inner = inner.next
				
			
			outer = auxiliary
		
	
	# Sum the all elements which are occurs in odd number of team
	def sum_odd_frequency_nodes(self) :
		if (self.head == None) :
			# When linked list is empty
			return
		
		# Grouping of similar nodes elements
		self.group_element()
		# Use to iterating linked list nodes
		outer = self.head
		inner = None
		# Define resultant variables
		counter = 0
		result = 0
		#  This loop takes O(N) time to find the frequency of all nodes
		while (outer != None) :
			# Set node counter
			counter = 1
			# start to next node
			inner = outer.next
			# Count repeated nodes
			while (inner != None and inner.data == outer.data) :
				counter += 1
				inner = inner.next
			
			if ((counter % 2) != 0) :
				if (outer != self.head) :
					print(" +", end = "")
				
				print(" ({0}x{1})".format(outer.data ,counter), end = "")
				# When odd frequency node get
				result += (outer.data) * counter
			
			# Get next frequency node in list
			outer = inner
		
		print("\n Odd frequency node sum is : ", result ,"\n", end = "")
	

def main() :
	obj = MyLinkedList()
	# Create linked list
	obj.insert(4)
	obj.insert(7)
	obj.insert(2)
	obj.insert(3)
	obj.insert(4)
	obj.insert(3)
	obj.insert(4)
	obj.insert(3)
	obj.insert(2)
	obj.insert(4)
	obj.insert(4)
	# Display of linked list nodes
	obj.display()
	obj.sum_odd_frequency_nodes()

if __name__ == "__main__": main()

Output

 Linked List :    4   7   2   3   4   3   4   3   2   4   4
 (4x5) + (3x3) + (7x1)
 Odd frequency node sum is :  36
#  Ruby Program
#  Sum of all odd frequency nodes of the linked list

# Node of LinkedList
class Node 

	# Define the accessor and reader of class Node  
	attr_reader :data, :next
	attr_accessor :data, :next
	
	def initialize(data)
	
		# Set node value
		self.data = data
		self.next = nil
	end
end
class MyLinkedList 

	# Define the accessor and reader of class MyLinkedList  
	attr_reader :head, :tail
	attr_accessor :head, :tail
	
	# Class constructors
	def initialize()
	
		self.head = nil
		self.tail = nil
	end
	# insert node at last of linke list
	def insert(data)
	
		# Create a node
		node = Node.new(data)
		if (self.head == nil)
		
			# When linked list empty add first node
			self.head = node
			self.tail = node
		else
		
			# Add new node at end of linked list
			self.tail.next = node
			self.tail = node
		end
	end
	# Display linked list element
	def display()
	
		if (self.head == nil)
		
			print("\nEmpty linked list\n")
			return
		end
		temp = self.head
		print("\n Linked List : ")
		while (temp != nil)
		
			print("  ", temp.data)
			temp = temp.next
		end
		print("\n")
	end
	#  This function are takes O(N^2) time to combine similar elements
	def group_element()
	
		# Define some auxiliary variables
		outer = self.head
		inner = nil
		auxiliary = nil
		temp = 0
		while (outer != nil)
		
			auxiliary = outer.next
			inner = auxiliary
			while (inner != nil && auxiliary != nil)
			
				if (auxiliary.data == outer.data)
				
					# visit to next node
					auxiliary = auxiliary.next
					if (auxiliary != nil)
					
						inner = auxiliary.next
					else
					
						inner = auxiliary
					end
				elsif(outer.data == inner.data)
				
					# Swap node value
					temp = auxiliary.data
					auxiliary.data = inner.data
					inner.data = temp
					# visit to next upcomming nodes
					auxiliary = auxiliary.next
					inner = inner.next
				else
				
					inner = inner.next
				end
			end
			outer = auxiliary
		end
	end
	# Sum the all elements which are occurs in odd number of team
	def sum_odd_frequency_nodes()
	
		if (self.head == nil)
		
			# When linked list is empty
			return
		end
		# Grouping of similar nodes elements
		self.group_element()
		# Use to iterating linked list nodes
		outer = self.head
		inner = nil
		# Define resultant variables
		counter = 0
		result = 0
		#  This loop takes O(N) time to find the frequency of all nodes
		while (outer != nil)
		
			# Set node counter
			counter = 1
			# start to next node
			inner = outer.next
			# Count repeated nodes
			while (inner != nil && inner.data == outer.data)
			
				counter += 1
				inner = inner.next
			end
			if ((counter % 2) != 0)
			
				if (outer != @head)
				
					print("+")
				end
				print(" (", outer.data ,"x", counter ,")")
				# When odd frequency node get
				result += (outer.data) * counter
			end
			# Get next frequency node in list
			outer = inner
		end
		print("\n Odd frequency node sum is : ", result ,"\n")
	end
end
def main()

	obj = MyLinkedList.new()
	# Create linked list
	obj.insert(4)
	obj.insert(7)
	obj.insert(2)
	obj.insert(3)
	obj.insert(4)
	obj.insert(3)
	obj.insert(4)
	obj.insert(3)
	obj.insert(2)
	obj.insert(4)
	obj.insert(4)
	# Display of linked list nodes
	obj.display()
	obj.sum_odd_frequency_nodes()
end
main()

Output

 Linked List :   4  7  2  3  4  3  4  3  2  4  4
 (4x5)+ (3x3)+ (7x1)
 Odd frequency node sum is : 36
// Scala Program
// Sum of all odd frequency nodes of the linked list

//Node of LinkedList
class Node(var data: Int,
	var next: Node)
{
	def this(data: Int)
	{
		this(data, null);
	}
}
class MyLinkedList(var head: Node,
	var tail: Node)
{
	//Class constructors
	def this()
	{
		this(null, null);
	}
	//insert node at last of linke list
	def insert(data: Int): Unit = {
		//Create a node
		var node: Node = new Node(data);
		if (this.head == null)
		{
			//When linked list empty add first node
			this.head = node;
			this.tail = node;
		}
		else
		{
			//Add new node at end of linked list
			this.tail.next = node;
			this.tail = node;
		}
	}
	//Display linked list element
	def display(): Unit = {
		if (this.head == null)
		{
			print("\nEmpty linked list\n");
			return;
		}
		var temp: Node = this.head;
		print("\n Linked List : ");
		while (temp != null)
		{
			print("  " + temp.data);
			temp = temp.next;
		}
		print("\n");
	}
	// This function are takes O(N^2) time to combine similar elements
	def group_element(): Unit = {
		//Define some auxiliary variables
		var outer: Node = this.head;
		var inner: Node = null;
		var auxiliary: Node = null;
		var temp: Int = 0;
		while (outer != null)
		{
			auxiliary = outer.next;
			inner = auxiliary;
			while (inner != null && auxiliary != null)
			{
				if (auxiliary.data == outer.data)
				{
					//visit to next node
					auxiliary = auxiliary.next;
					if (auxiliary != null)
					{
						inner = auxiliary.next;
					}
					else
					{
						inner = auxiliary;
					}
				}
				else if (outer.data == inner.data)
				{
					//Swap node value
					temp = auxiliary.data;
					auxiliary.data = inner.data;
					inner.data = temp;
					//visit to next upcomming nodes
					auxiliary = auxiliary.next;
					inner = inner.next;
				}
				else
				{
					inner = inner.next;
				}
			}
			outer = auxiliary;
		}
	}
	//Sum the all elements which are occurs in odd number of team
	def sum_odd_frequency_nodes(): Unit = {
		if (this.head == null)
		{
			//When linked list is empty
			return;
		}
		//Grouping of similar nodes elements
		this.group_element();
		//Use to iterating linked list nodes
		var outer: Node = this.head;
		var inner: Node = null;
		//Define resultant variables
		var counter: Int = 0;
		var result: Int = 0;
		// This loop takes O(N) time to find the frequency of all nodes
		while (outer != null)
		{
			//Set node counter
			counter = 1;
			//start to next node
			inner = outer.next;
			//Count repeated nodes
			while (inner != null && inner.data == outer.data)
			{
				counter += 1;
				inner = inner.next;
			}
			if ((counter % 2) != 0)
			{
				if (outer != head)
				{
					print(" +");
				}
				print(" (" + outer.data + "x" + counter + ")");
				//When odd frequency node get
				result += (outer.data) * counter;
			}
			//Get next frequency node in list
			outer = inner;
		}
		print("\n Odd frequency node sum is : " + result + "\n");
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: MyLinkedList = new MyLinkedList();
		//Create linked list
		obj.insert(4);
		obj.insert(7);
		obj.insert(2);
		obj.insert(3);
		obj.insert(4);
		obj.insert(3);
		obj.insert(4);
		obj.insert(3);
		obj.insert(2);
		obj.insert(4);
		obj.insert(4);
		//Display of linked list nodes
		obj.display();
		obj.sum_odd_frequency_nodes();
	}
}

Output

 Linked List :   4  7  2  3  4  3  4  3  2  4  4
 (4x5) + (3x3) + (7x1)
 Odd frequency node sum is : 36
// Swift Program
// Sum of all odd frequency nodes of the linked list

//Node of LinkedList
class Node
{
	var data: Int;
	var next: Node? ;
	init(_ data: Int)
	{
		//Set node value
		self.data = data;
		self.next = nil;
	}
}
class MyLinkedList
{
	var head: Node? ;
	var tail: Node? ;
	//Class constructors
	init()
	{
		self.head = nil;
		self.tail = nil;
	}
	//insert node at last of linke list
	func insert(_ data: Int)
	{
		//Create a node
		let node: Node? = Node(data);
		if (self.head == nil)
		{
			//When linked list empty add first node
			self.head = node;
			self.tail = node;
		}
		else
		{
			//Add new node at end of linked list
			self.tail!.next = node;
			self.tail = node;
		}
	}
	//Display linked list element
	func display()
	{
		if (self.head == nil)
		{
			print("\nEmpty linked list\n", terminator: "");
			return;
		}
		var temp: Node? = self.head;
		print("\n Linked List : ", terminator: "");
		while (temp != nil)
		{
			print("  ", temp!.data, terminator: "");
			temp = temp!.next;
		}
		print("\n", terminator: "");
	}
	// This function are takes O(N^2) time to combine similar elements
	func group_element()
	{
		//Define some auxiliary variables
		var outer: Node? = self.head;
		var inner: Node? = nil;
		var auxiliary: Node? = nil;
		var temp: Int = 0;
		while (outer != nil)
		{
			auxiliary = outer!.next;
			inner = auxiliary;
			while (inner != nil && auxiliary != nil)
			{
				if (auxiliary!.data == outer!.data)
				{
					//visit to next node
					auxiliary = auxiliary!.next;
					if (auxiliary != nil)
					{
						inner = auxiliary!.next;
					}
					else
					{
						inner = auxiliary;
					}
				}
				else if (outer!.data == inner!.data)
				{
					//Swap node value
					temp = auxiliary!.data;
					auxiliary!.data = inner!.data;
					inner!.data = temp;
					//visit to next upcomming nodes
					auxiliary = auxiliary!.next;
					inner = inner!.next;
				}
				else
				{
					inner = inner!.next;
				}
			}
			outer = auxiliary;
		}
	}
	//Sum the all elements which are occurs in odd number of team
	func sum_odd_frequency_nodes()
	{
		if (self.head == nil)
		{
			//When linked list is empty
			return;
		}
		//Grouping of similar nodes elements
		self.group_element();
		//Use to iterating linked list nodes
		var outer: Node? = self.head;
		var inner: Node? = nil;
		//Define resultant variables
		var counter: Int = 0;
		var result: Int = 0;
		// This loop takes O(N) time to find the frequency of all nodes
		while (outer != nil)
		{
			//Set node counter
			counter = 1;
			//start to next node
			inner = outer!.next;
			//Count repeated nodes
			while (inner != nil && inner!.data == outer!.data)
			{
				counter += 1;
				inner = inner!.next;
			}
			if ((counter % 2) != 0)
			{
				if (!(outer === self.head))
				{
					print(" +", terminator: "");
				}
				print(" (\(outer!.data)x\(counter))", terminator: "");
				//When odd frequency node get
				result += (outer!.data) * counter;
			}
			//Get next frequency node in list
			outer = inner;
		}
		print("\n Odd frequency node sum is : ", result ,"\n", terminator: "");
	}
}
func main()
{
	let obj: MyLinkedList = MyLinkedList();
	//Create linked list
	obj.insert(4);
	obj.insert(7);
	obj.insert(2);
	obj.insert(3);
	obj.insert(4);
	obj.insert(3);
	obj.insert(4);
	obj.insert(3);
	obj.insert(2);
	obj.insert(4);
	obj.insert(4);
	//Display of linked list nodes
	obj.display();
	obj.sum_odd_frequency_nodes();
}
main();

Output

 Linked List :    4   7   2   3   4   3   4   3   2   4   4
 (4x5) + (3x3) + (7x1)
 Odd frequency node sum is :  36




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment