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
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