Sort the linked list elements by node frequency

Given a linked list, its node include the value of the integer element. Our goal is to arrange linked list element by node element frequency (lower to higher order).

Example 1 :
------------
2 → 2 → 6 → 3 → 6 → 2 → NULL
Here frequency
2 -> 3 times
6 -> 2 times
3 -> 1 times

So sorted frequency
3 -> 1 times
6 -> 2 times
2 -> 3 times

Output 
3 → 6 → 6 → 2 → 2 → 2 → NULL
Example 2
----------
1 → 1 → 2 → 3 → 2 → 1 → 3 →NULL
Here frequency
1 -> 3 times
2 -> 2 times
3 -> 2 times

So sorted frequency
2 -> 2 times
3 -> 2 times [Same frequency]
1 -> 3 times

Output
2 → 2 → 3 → 3 → 1 → 1 → 1 →NULL
or [because 2 and 3 are exist in same frequency]
3 → 3 → 2 → 2 → 1 → 1 → 1 →NULL
[Note that when 2 or more frequency are same 
 Then there element sequences appearance not important]

Here given code implementation process.

// C Program 
// Sort the linked list elements by node frequency
#include <stdio.h>

#include <stdlib.h> //for malloc function

//Linked List Node
struct Node
{
	int data;
	struct Node *next;
};
//Linked List Node
struct Frequency
{
	int key;
	int counter;
	struct Frequency *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 
struct Node *add_node(struct Node *tail, int data)
{
	struct Node *node = create_node(data);
	if (tail != NULL)
	{
		tail->next = node;
	}
	return node;
}
struct Frequency *add_frequency(struct Frequency *collection, int key, int counter)
{
	//Create dynamic node
	struct Frequency *element = (struct Frequency *) malloc(sizeof(struct Frequency));
	if (element == NULL)
	{
		printf("Memory overflow\n");
	}
	else
	{
		// Add the value of new element 
		element->key = key;
		element->counter = counter;
		element->next = NULL;
		if (collection == NULL)
		{
			return element;
		}
		else if (collection->counter >= counter)
		{
			//When need to add node at beginning
			element->next = collection;
			return element;
		}
		else
		{
			//sorted add new node
			struct Frequency *temp = collection;
			while (temp != NULL && temp->next != NULL && temp->next->counter < counter)
			{
				//visit to next node
				temp = temp->next;
			}
			element->next = temp->next;
			//add element into given collection
			temp->next = element;
		}
	}
	return collection;
}
//Display linked list element
void display(struct Node *head)
{
	if (head == NULL)
	{
		printf("\n Empty linked list\n");
		return;
	}
	struct Node *temp = head;
	//iterating linked list elements
	while (temp != NULL)
	{
		if (temp != head)
		{
			printf(" →");
		}
		printf(" %d", temp->data);
		//visit to next node
		temp = temp->next;
	}
	printf(" → NULL\n");
}
struct Node *count_and_delete(struct Node *first, int *counter, int key)
{
	//Define some auxiliary variables
	struct Node *current = first;
	struct Node *front = first;
	struct Node *auxiliary = NULL;
	struct Node *back = NULL;
	first = NULL;
	//iterating linked list elements
	while (current != NULL)
	{
		if (current->data == key)
		{
			//When get delete node node
			auxiliary = current;
			//node counter
			*counter = ( *counter) + 1;
		}
		else
		{
			back = current;
		}
		//visit to next node
		current = current->next;
		if (auxiliary != NULL)
		{
			//When Deleted node exists
			if (back == NULL)
			{
				// When front node is delete
				// head visit to next node
				front = current;
			}
			else
			{
				// Deleted node are exist in intermediate or last position of linked list
				// Before delete node, there left node is connecting to next upcoming node
				back->next = current;
			}
			//unlink deleted node 
			auxiliary->next = NULL;
			//free node
			free(auxiliary);
			auxiliary = NULL;
		}
	}
	return front;
}
void sort_by_frequency(struct Node **head, struct Node **tail)
{
	if (head == NULL)
	{
		printf("\n Empty linked List");
	}
	else
	{
		struct Frequency *collection = NULL;
		struct Frequency *temp = NULL;
		int counter = 0;
		int key = 0;
		struct Node *current = *head;
		//set last node to null
		*tail = NULL;
		//Count node frequency and arrange in sorted order
		while (current != NULL)
		{
			key = current->data;*head = count_and_delete( *head, &counter, key);
			collection = add_frequency(collection, key, counter);
			current = *head;
			counter = 0;
		}
		while (collection != NULL)
		{
			counter = collection->counter;
			key = collection->key;
			while (counter > 0)
			{
				*tail = add_node( *tail, key);
				if ( *head == NULL)
				{
					*head = *tail;
				}
				counter--;
			}
			temp = collection;
			//visit to next node
			collection = collection->next;
			//Free node
			temp->next = NULL;
			free(temp);
			temp = NULL;
		}
	}
}
int main()
{
	struct Node *head = NULL;
	struct Node *tail = NULL;
	// Add linked list node
	head = tail = add_node(tail, 2);
	tail = add_node(tail, 6);
	tail = add_node(tail, 7);
	tail = add_node(tail, 6);
	tail = add_node(tail, 3);
	tail = add_node(tail, 6);
	tail = add_node(tail, 2);
	tail = add_node(tail, 3);
	tail = add_node(tail, 1);
	tail = add_node(tail, 7);
	tail = add_node(tail, 3);
	tail = add_node(tail, 6);
	tail = add_node(tail, 7);
	tail = add_node(tail, 1);
	tail = add_node(tail, 5);
	tail = add_node(tail, 6);
	tail = add_node(tail, 9);
	tail = add_node(tail, 3);
	printf("Before sort by frequency\n");
	// 2 → 6 → 7 → 6 → 3 → 6 → 2 → 3 → 1 → 7 → 3 → 6 → 7 → 1 → 5 → 6 → 9 → 3 → NULL
	display(head);
	sort_by_frequency( &head, &tail);
	printf("Before sort by frequency\n");
	//9 → 5 → 1 → 1 → 2 → 2 → 7 → 7 → 7 → 3 → 3 → 3 → 3 → 6 → 6 → 6 → 6 → 6 → NULL
	display(head);
	return 0;
}

Output

Before sort by frequency
 2 → 6 → 7 → 6 → 3 → 6 → 2 → 3 → 1 → 7 → 3 → 6 → 7 → 1 → 5 → 6 → 9 → 3 → NULL
Before sort by frequency
 9 → 5 → 1 → 1 → 2 → 2 → 7 → 7 → 7 → 3 → 3 → 3 → 3 → 6 → 6 → 6 → 6 → 6 → NULL
//Include header file
#include <iostream>

using namespace std;
// C++ Program
// Sort the linked list elements by node frequency
//Node of LinkedList
class Node
{
	public: int data;
	Node *next;
	Node(int data)
	{
		//Set node value
		this->data = data;
		this->next = NULL;
	}
};
class Frequency
{
	public: int key;
	int counter;
	Frequency *next;
	Frequency(int key, int size)
	{
		//Set node value
		this->key = key;
		this->counter = size;
		this->next = NULL;
	}
};
class MyLinkedList
{
	public: Node *head;
	Node *tail;
	//Class constructor
	MyLinkedList()
	{
		this->head = NULL;
		this->tail = NULL;
	}
	//insert node at last of linke list
	void add_node(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 << "Linked List : ";
		//iterating linked list elements
		while (temp != NULL)
		{
			if (temp != this->head)
			{
				cout << " →";
			}
			cout << " " << temp->data;
			//visit to next node
			temp = temp->next;
		}
		cout << " → NULL\n";
	}
	Frequency *add_frequency(Frequency *collection, int key, int counter)
	{
		Frequency *element = new Frequency(key, counter);
		if (element == NULL)
		{
			cout << "Memory overflow\n";
		}
		else
		{
			if (collection == NULL)
			{
				return element;
			}
			else if (collection->counter >= counter)
			{
				//When need to add node at beginning
				element->next = collection;
				return element;
			}
			else
			{
				//Sorted add new node
				Frequency *temp = collection;
				while (temp != NULL && temp->next != NULL && temp->next->counter < counter)
				{
					//visit to next node
					temp = temp->next;
				}
				element->next = temp->next;
				//add element into given collection
				temp->next = element;
			}
		}
		return collection;
	}
	//Count and delete node which value is equal to front node
	int count_and_delete()
	{
		int key = this->head->data;
		//Define some auxiliary variables
		Node *current = this->head;
		Node *auxiliary = NULL;
		Node *back = NULL;
		int counter = 0;
		//iterating linked list elements
		while (current != NULL)
		{
			if (current->data == key)
			{
				//When get delete node node
				auxiliary = current;
				//node counter
				counter = counter + 1;
			}
			else
			{
				back = current;
			}
			//visit to next node
			current = current->next;
			if (auxiliary != NULL)
			{
				//When Deleted node exists
				if (this->head == auxiliary)
				{
					// When delete first node
					// head visit to next node
					this->head = current;
				}
				else
				{
					// Deleted node are exist in intermediate or last position of linked list
					// Before delete node, there left node is connecting to next upcoming node
					back->next = current;
				}
				//unlink deleted node 
				auxiliary->next = NULL;
				//free node
				auxiliary = NULL;
			}
		}
		return counter;
	}
	void sort_by_frequency()
	{
		if (this->head == NULL)
		{
			cout << "\n Empty linked List";
		}
		else
		{
			Frequency *collection = NULL;
			Frequency *temp = NULL;
			int counter = 0;
			int key = 0;
			Node *current = this->head;
			//Set last node to null
			this->tail = NULL;
			//Count node frequency and arrange in sorted order
			while (current != NULL)
			{
				key = current->data;
				counter = this->count_and_delete();
				collection = this->add_frequency(collection, key, counter);
				current = this->head;
			}
			// Add node in linked list by node frequency
			while (collection != NULL)
			{
				counter = collection->counter;
				key = collection->key;
				while (counter > 0)
				{
					this->add_node(key);
					counter--;
				}
				temp = collection;
				//visit to next node
				collection = collection->next;
				//Free node
				temp->next = NULL;
				delete temp;
				temp = NULL;
			}
		}
	}
};
int main()
{
	MyLinkedList obj = MyLinkedList();
	// Add linked list node
	obj.add_node(2);
	obj.add_node(6);
	obj.add_node(7);
	obj.add_node(6);
	obj.add_node(3);
	obj.add_node(6);
	obj.add_node(2);
	obj.add_node(3);
	obj.add_node(1);
	obj.add_node(7);
	obj.add_node(3);
	obj.add_node(6);
	obj.add_node(7);
	obj.add_node(1);
	obj.add_node(5);
	obj.add_node(6);
	obj.add_node(9);
	obj.add_node(3);
	cout << "Before sort by frequency\n";
	// 2 → 6 → 7 → 6 → 3 → 6 → 2 → 3 → 1 → 7 → 3 → 6 → 7 → 1 → 5 → 6 → 9 → 3 → NULL
	obj.display();
	obj.sort_by_frequency();
	cout << "Before sort by frequency\n";
	//9 → 5 → 1 → 1 → 2 → 2 → 7 → 7 → 7 → 3 → 3 → 3 → 3 → 6 → 6 → 6 → 6 → 6 → NULL
	obj.display();
	return 0;
}

Output

Before sort by frequency
Linked List :  2 → 6 → 7 → 6 → 3 → 6 → 2 → 3 → 1 → 7 → 3 → 6 → 7 → 1 → 5 → 6 → 9 → 3 → NULL
Before sort by frequency
Linked List :  9 → 5 → 1 → 1 → 2 → 2 → 7 → 7 → 7 → 3 → 3 → 3 → 3 → 6 → 6 → 6 → 6 → 6 → NULL
// Java Program
// Sort the linked list elements by node frequency

//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 Frequency
{
	public int key;
	public int counter;
	public Frequency next;
	public Frequency(int key, int size)
	{
		//Set node value
		this.key = key;
		this.counter = size;
		this.next = null;
	}
}
class MyLinkedList
{
	public Node head;
	public Node tail;
	//Class constructor
	public MyLinkedList()
	{
		this.head = null;
		this.tail = null;
	}
	//insert node at last of linke list
	public void add_node(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("Linked List : ");
		//iterating linked list elements
		while (temp != null)
		{
			if (temp != this.head)
			{
				System.out.print(" →");
			}
			System.out.print(" " + temp.data);
			//visit to next node
			temp = temp.next;
		}
		System.out.print(" → NULL\n");
	}
	public Frequency add_frequency(Frequency collection, int key, int counter)
	{
		Frequency element = new Frequency(key, counter);
		if (element == null)
		{
			System.out.print("Memory overflow\n");
		}
		else
		{
			if (collection == null)
			{
				return element;
			}
			else if (collection.counter >= counter)
			{
				//When need to add node at beginning
				element.next = collection;
				return element;
			}
			else
			{
				//Sorted add new node
				Frequency temp = collection;
				while (temp != null && temp.next != null && temp.next.counter < counter)
				{
					//visit to next node
					temp = temp.next;
				}
				element.next = temp.next;
				//add element into given collection
				temp.next = element;
			}
		}
		return collection;
	}
	//Count and delete node which value is equal to front node
	public int count_and_delete()
	{
		int key = this.head.data;
		//Define some auxiliary variables
		Node current = this.head;
		Node auxiliary = null;
		Node back = null;
		int counter = 0;
		//iterating linked list elements
		while (current != null)
		{
			if (current.data == key)
			{
				//When get delete node node
				auxiliary = current;
				//node counter
				counter = counter + 1;
			}
			else
			{
				back = current;
			}
			//visit to next node
			current = current.next;
			if (auxiliary != null)
			{
				//When Deleted node exists
				if (this.head == auxiliary)
				{
					// When delete first node
					// head visit to next node
					this.head = current;
				}
				else
				{
					// Deleted node are exist in intermediate or last position of linked list
					// Before delete node, there left node is connecting to next upcoming node
					back.next = current;
				}
				//unlink deleted node 
				auxiliary.next = null;
				//free node
				auxiliary = null;
			}
		}
		return counter;
	}
	public void sort_by_frequency()
	{
		if (this.head == null)
		{
			System.out.print("\n Empty linked List");
		}
		else
		{
			Frequency collection = null;
			Frequency temp = null;
			int counter = 0;
			int key = 0;
			Node current = this.head;
			//Set last node to null
			this.tail = null;
			//Count node frequency and arrange in sorted order
			while (current != null)
			{
				key = current.data;
				counter = count_and_delete();
				collection = add_frequency(collection, key, counter);
				current = this.head;
			}
			// Add node in linked list by node frequency
			while (collection != null)
			{
				counter = collection.counter;
				key = collection.key;
				while (counter > 0)
				{
					this.add_node(key);
					counter--;
				}
				temp = collection;
				//visit to next node
				collection = collection.next;
				//Free node
				temp.next = null;
				temp = null;
			}
		}
	}
	public static void main(String[] args)
	{
		MyLinkedList obj = new MyLinkedList();
		// Add linked list node
		obj.add_node(2);
		obj.add_node(6);
		obj.add_node(7);
		obj.add_node(6);
		obj.add_node(3);
		obj.add_node(6);
		obj.add_node(2);
		obj.add_node(3);
		obj.add_node(1);
		obj.add_node(7);
		obj.add_node(3);
		obj.add_node(6);
		obj.add_node(7);
		obj.add_node(1);
		obj.add_node(5);
		obj.add_node(6);
		obj.add_node(9);
		obj.add_node(3);
		System.out.print("Before sort by frequency\n");
		// 2 → 6 → 7 → 6 → 3 → 6 → 2 → 3 → 1 → 7 → 3 → 6 → 7 → 1 → 5 → 6 → 9 → 3 → NULL
		obj.display();
		obj.sort_by_frequency();
		System.out.print("Before sort by frequency\n");
		//9 → 5 → 1 → 1 → 2 → 2 → 7 → 7 → 7 → 3 → 3 → 3 → 3 → 6 → 6 → 6 → 6 → 6 → NULL
		obj.display();
	}
}

Output

Before sort by frequency
Linked List :  2 → 6 → 7 → 6 → 3 → 6 → 2 → 3 → 1 → 7 → 3 → 6 → 7 → 1 → 5 → 6 → 9 → 3 → NULL
Before sort by frequency
Linked List :  9 → 5 → 1 → 1 → 2 → 2 → 7 → 7 → 7 → 3 → 3 → 3 → 3 → 6 → 6 → 6 → 6 → 6 → NULL
//Include namespace system
using System;
// C# Program
// Sort the linked list elements by node frequency

//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 Frequency
{
	public int key;
	public int counter;
	public Frequency next;
	public Frequency(int key, int size)
	{
		//Set node value
		this.key = key;
		this.counter = size;
		this.next = null;
	}
}
class MyLinkedList
{
	public Node head;
	public Node tail;
	//Class constructor
	public MyLinkedList()
	{
		this.head = null;
		this.tail = null;
	}
	//insert node at last of linke list
	public void add_node(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("Linked List : ");
		//iterating linked list elements
		while (temp != null)
		{
			if (temp != this.head)
			{
				Console.Write(" →");
			}
			Console.Write(" " + temp.data);
			//visit to next node
			temp = temp.next;
		}
		Console.Write(" → NULL\n");
	}
	public Frequency add_frequency(Frequency collection, int key, int counter)
	{
		Frequency element = new Frequency(key, counter);
		if (element == null)
		{
			Console.Write("Memory overflow\n");
		}
		else
		{
			if (collection == null)
			{
				return element;
			}
			else if (collection.counter >= counter)
			{
				//When need to add node at beginning
				element.next = collection;
				return element;
			}
			else
			{
				//Sorted add new node
				Frequency temp = collection;
				while (temp != null && temp.next != null && temp.next.counter < counter)
				{
					//visit to next node
					temp = temp.next;
				}
				element.next = temp.next;
				//add element into given collection
				temp.next = element;
			}
		}
		return collection;
	}
	//Count and delete node which value is equal to front node
	public int count_and_delete()
	{
		int key = this.head.data;
		//Define some auxiliary variables
		Node current = this.head;
		Node auxiliary = null;
		Node back = null;
		int counter = 0;
		//iterating linked list elements
		while (current != null)
		{
			if (current.data == key)
			{
				//When get delete node node
				auxiliary = current;
				//node counter
				counter = counter + 1;
			}
			else
			{
				back = current;
			}
			//visit to next node
			current = current.next;
			if (auxiliary != null)
			{
				//When Deleted node exists
				if (this.head == auxiliary)
				{
					// When delete first node
					// head visit to next node
					this.head = current;
				}
				else
				{
					// Deleted node are exist in intermediate or last position of linked list
					// Before delete node, there left node is connecting to next upcoming node
					back.next = current;
				}
				//unlink deleted node 
				auxiliary.next = null;
				//free node
				auxiliary = null;
			}
		}
		return counter;
	}
	public void sort_by_frequency()
	{
		if (this.head == null)
		{
			Console.Write("\n Empty linked List");
		}
		else
		{
			Frequency collection = null;
			Frequency temp = null;
			int counter = 0;
			int key = 0;
			Node current = this.head;
			//Set last node to null
			this.tail = null;
			//Count node frequency and arrange in sorted order
			while (current != null)
			{
				key = current.data;
				counter = count_and_delete();
				collection = add_frequency(collection, key, counter);
				current = this.head;
			}
			// Add node in linked list by node frequency
			while (collection != null)
			{
				counter = collection.counter;
				key = collection.key;
				while (counter > 0)
				{
					this.add_node(key);
					counter--;
				}
				temp = collection;
				//visit to next node
				collection = collection.next;
				//Free node
				temp.next = null;
				temp = null;
			}
		}
	}
	public static void Main(String[] args)
	{
		MyLinkedList obj = new MyLinkedList();
		// Add linked list node
		obj.add_node(2);
		obj.add_node(6);
		obj.add_node(7);
		obj.add_node(6);
		obj.add_node(3);
		obj.add_node(6);
		obj.add_node(2);
		obj.add_node(3);
		obj.add_node(1);
		obj.add_node(7);
		obj.add_node(3);
		obj.add_node(6);
		obj.add_node(7);
		obj.add_node(1);
		obj.add_node(5);
		obj.add_node(6);
		obj.add_node(9);
		obj.add_node(3);
		Console.Write("Before sort by frequency\n");
		// 2 → 6 → 7 → 6 → 3 → 6 → 2 → 3 → 1 → 7 → 3 → 6 → 7 → 1 → 5 → 6 → 9 → 3 → NULL
		obj.display();
		obj.sort_by_frequency();
		Console.Write("Before sort by frequency\n");
		//9 → 5 → 1 → 1 → 2 → 2 → 7 → 7 → 7 → 3 → 3 → 3 → 3 → 6 → 6 → 6 → 6 → 6 → NULL
		obj.display();
	}
}

Output

Before sort by frequency
Linked List :  2 → 6 → 7 → 6 → 3 → 6 → 2 → 3 → 1 → 7 → 3 → 6 → 7 → 1 → 5 → 6 → 9 → 3 → NULL
Before sort by frequency
Linked List :  9 → 5 → 1 → 1 → 2 → 2 → 7 → 7 → 7 → 3 → 3 → 3 → 3 → 6 → 6 → 6 → 6 → 6 → NULL
<?php
// Php Program
// Sort the linked list elements by node frequency

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

	function __construct($data)
	{
		//Set node value
		$this->data = $data;
		$this->next = null;
	}
}
class Frequency
{
	public $key;
	public $counter;
	public $next;

	function __construct($key, $size)
	{
		//Set node value
		$this->key = $key;
		$this->counter = $size;
		$this->next = null;
	}
}
class MyLinkedList
{
	public $head;
	public $tail;
	//Class constructor
	function __construct()
	{
		$this->head = null;
		$this->tail = null;
	}
	//insert node at last of linke list
	public	function add_node($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 "Linked List : ";
		//iterating linked list elements
		while ($temp != null)
		{
			if ($temp != $this->head)
			{
				echo " →";
			}
			echo " ". $temp->data;
			//visit to next node
			$temp = $temp->next;
		}
		echo " → NULL\n";
	}
	public	function add_frequency($collection, $key, $counter)
	{
		$element = new Frequency($key, $counter);
		if ($element == null)
		{
			echo "Memory overflow\n";
		}
		else
		{
			if ($collection == null)
			{
				return $element;
			}
			else if ($collection->counter >= $counter)
			{
				//When need to add node at beginning
				$element->next = $collection;
				return $element;
			}
			else
			{
				//Sorted add new node
				$temp = $collection;
				while ($temp != null && $temp->next != null && $temp->next->counter < $counter)
				{
					//visit to next node
					$temp = $temp->next;
				}
				$element->next = $temp->next;
				//add element into given collection
				$temp->next = $element;
			}
		}
		return $collection;
	}
	//Count and delete node which value is equal to front node
	public	function count_and_delete()
	{
		$key = $this->head->data;
		//Define some auxiliary variables
		$current = $this->head;
		$auxiliary = null;
		$back = null;
		$counter = 0;
		//iterating linked list elements
		while ($current != null)
		{
			if ($current->data == $key)
			{
				//When get delete node node
				$auxiliary = $current;
				//node counter
				$counter = $counter + 1;
			}
			else
			{
				$back = $current;
			}
			//visit to next node
			$current = $current->next;
			if ($auxiliary != null)
			{
				//When Deleted node exists
				if ($this->head == $auxiliary)
				{
					// When delete first node
					// head visit to next node
					$this->head = $current;
				}
				else
				{
					// Deleted node are exist in intermediate or last position of linked list
					// Before delete node, there left node is connecting to next upcoming node
					$back->next = $current;
				}
				//unlink deleted node 
				$auxiliary->next = null;
				//free node
				$auxiliary = null;
			}
		}
		return $counter;
	}
	public	function sort_by_frequency()
	{
		if ($this->head == null)
		{
			echo "\n Empty linked List";
		}
		else
		{
			$collection = null;
			$temp = null;
			$counter = 0;
			$key = 0;
			$current = $this->head;
			//Set last node to null
			$this->tail = null;
			//Count node frequency and arrange in sorted order
			while ($current != null)
			{
				$key = $current->data;
				$counter = $this->count_and_delete();
				$collection = $this->add_frequency($collection, $key, $counter);
				$current = $this->head;
			}
			// Add node in linked list by node frequency
			while ($collection != null)
			{
				$counter = $collection->counter;
				$key = $collection->key;
				while ($counter > 0)
				{
					$this->add_node($key);
					$counter--;
				}
				$temp = $collection;
				//visit to next node
				$collection = $collection->next;
				//Free node
				$temp->next = null;
				$temp = null;
			}
		}
	}
}

function main()
{
	$obj = new MyLinkedList();
	// Add linked list node
	$obj->add_node(2);
	$obj->add_node(6);
	$obj->add_node(7);
	$obj->add_node(6);
	$obj->add_node(3);
	$obj->add_node(6);
	$obj->add_node(2);
	$obj->add_node(3);
	$obj->add_node(1);
	$obj->add_node(7);
	$obj->add_node(3);
	$obj->add_node(6);
	$obj->add_node(7);
	$obj->add_node(1);
	$obj->add_node(5);
	$obj->add_node(6);
	$obj->add_node(9);
	$obj->add_node(3);
	echo "Before sort by frequency\n";
	// 2 → 6 → 7 → 6 → 3 → 6 → 2 → 3 → 1 → 7 → 3 → 6 → 7 → 1 → 5 → 6 → 9 → 3 → NULL
	$obj->display();
	$obj->sort_by_frequency();
	echo "Before sort by frequency\n";
	//9 → 5 → 1 → 1 → 2 → 2 → 7 → 7 → 7 → 3 → 3 → 3 → 3 → 6 → 6 → 6 → 6 → 6 → NULL
	$obj->display();
}
main();

Output

Before sort by frequency
Linked List :  2 → 6 → 7 → 6 → 3 → 6 → 2 → 3 → 1 → 7 → 3 → 6 → 7 → 1 → 5 → 6 → 9 → 3 → NULL
Before sort by frequency
Linked List :  9 → 5 → 1 → 1 → 2 → 2 → 7 → 7 → 7 → 3 → 3 → 3 → 3 → 6 → 6 → 6 → 6 → 6 → NULL
// Node Js Program
// Sort the linked list elements by node frequency
//Node of LinkedList
class Node
{
	constructor(data)
	{
		//Set node value
		this.data = data;
		this.next = null;
	}
}
class Frequency
{
	constructor(key, size)
	{
		//Set node value
		this.key = key;
		this.counter = size;
		this.next = null;
	}
}
class MyLinkedList
{
	//Class constructor
	constructor()
	{
		this.head = null;
		this.tail = null;
	}
	//insert node at last of linke list
	add_node(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("Linked List : ");
		//iterating linked list elements
		while (temp != null)
		{
			if (temp != this.head)
			{
				process.stdout.write(" →");
			}
			process.stdout.write(" " + temp.data);
			//visit to next node
			temp = temp.next;
		}
		process.stdout.write(" → NULL\n");
	}
	add_frequency(collection, key, counter)
	{
		var element = new Frequency(key, counter);
		if (element == null)
		{
			process.stdout.write("Memory overflow\n");
		}
		else
		{
			if (collection == null)
			{
				return element;
			}
			else if (collection.counter >= counter)
			{
				//When need to add node at beginning
				element.next = collection;
				return element;
			}
			else
			{
				//Sorted add new node
				var temp = collection;
				while (temp != null && temp.next != null && temp.next.counter < counter)
				{
					//visit to next node
					temp = temp.next;
				}
				element.next = temp.next;
				//add element into given collection
				temp.next = element;
			}
		}
		return collection;
	}
	//Count and delete node which value is equal to front node
	count_and_delete()
	{
		var key = this.head.data;
		//Define some auxiliary variables
		var current = this.head;
		var auxiliary = null;
		var back = null;
		var counter = 0;
		//iterating linked list elements
		while (current != null)
		{
			if (current.data == key)
			{
				//When get delete node node
				auxiliary = current;
				//node counter
				counter = counter + 1;
			}
			else
			{
				back = current;
			}
			//visit to next node
			current = current.next;
			if (auxiliary != null)
			{
				//When Deleted node exists
				if (this.head == auxiliary)
				{
					// When delete first node
					// head visit to next node
					this.head = current;
				}
				else
				{
					// Deleted node are exist in intermediate or last position of linked list
					// Before delete node, there left node is connecting to next upcoming node
					back.next = current;
				}
				//unlink deleted node 
				auxiliary.next = null;
				//free node
				auxiliary = null;
			}
		}
		return counter;
	}
	sort_by_frequency()
	{
		if (this.head == null)
		{
			process.stdout.write("\n Empty linked List");
		}
		else
		{
			var collection = null;
			var temp = null;
			var counter = 0;
			var key = 0;
			var current = this.head;
			//Set last node to null
			this.tail = null;
			//Count node frequency and arrange in sorted order
			while (current != null)
			{
				key = current.data;
				counter = this.count_and_delete();
				collection = this.add_frequency(collection, key, counter);
				current = this.head;
			}
			// Add node in linked list by node frequency
			while (collection != null)
			{
				counter = collection.counter;
				key = collection.key;
				while (counter > 0)
				{
					this.add_node(key);
					counter--;
				}
				temp = collection;
				//visit to next node
				collection = collection.next;
				//Free node
				temp.next = null;
				temp = null;
			}
		}
	}
}

function main()
{
	var obj = new MyLinkedList();
	// Add linked list node
	obj.add_node(2);
	obj.add_node(6);
	obj.add_node(7);
	obj.add_node(6);
	obj.add_node(3);
	obj.add_node(6);
	obj.add_node(2);
	obj.add_node(3);
	obj.add_node(1);
	obj.add_node(7);
	obj.add_node(3);
	obj.add_node(6);
	obj.add_node(7);
	obj.add_node(1);
	obj.add_node(5);
	obj.add_node(6);
	obj.add_node(9);
	obj.add_node(3);
	process.stdout.write("Before sort by frequency\n");
	// 2 → 6 → 7 → 6 → 3 → 6 → 2 → 3 → 1 → 7 → 3 → 6 → 7 → 1 → 5 → 6 → 9 → 3 → NULL
	obj.display();
	obj.sort_by_frequency();
	process.stdout.write("Before sort by frequency\n");
	//9 → 5 → 1 → 1 → 2 → 2 → 7 → 7 → 7 → 3 → 3 → 3 → 3 → 6 → 6 → 6 → 6 → 6 → NULL
	obj.display();
}
main();

Output

Before sort by frequency
Linked List :  2 → 6 → 7 → 6 → 3 → 6 → 2 → 3 → 1 → 7 → 3 → 6 → 7 → 1 → 5 → 6 → 9 → 3 → NULL
Before sort by frequency
Linked List :  9 → 5 → 1 → 1 → 2 → 2 → 7 → 7 → 7 → 3 → 3 → 3 → 3 → 6 → 6 → 6 → 6 → 6 → NULL
#  Python 3 Program
#  Sort the linked list elements by node frequency

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

class Frequency :
	
	def __init__(self, key, size) :
		# Set node value
		self.key = key
		self.counter = size
		self.next = None
	

class MyLinkedList :
	
	# Class constructor
	def __init__(self) :
		self.head = None
		self.tail = None
	
	# insert node at last of linke list
	def add_node(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("Linked List : ", end = "")
		# iterating linked list elements
		while (temp != None) :
			if (temp != self.head) :
				print(" →", end = "")
			
			print(" ", temp.data, end = "")
			# visit to next node
			temp = temp.next
		
		print(" → NULL\n", end = "")
	
	def add_frequency(self, collection, key, counter) :
		element = Frequency(key, counter)
		if (element == None) :
			print("Memory overflow\n", end = "")
		else :
			if (collection == None) :
				return element
			
			elif(collection.counter >= counter) :
				# When need to add node at beginning
				element.next = collection
				return element
			else :
				# Sorted add new node
				temp = collection
				while (temp != None and temp.next != None and temp.next.counter < counter) :
					# visit to next node
					temp = temp.next
				
				element.next = temp.next
				# add element into given collection
				temp.next = element
			
		
		return collection
	
	# Count and delete node which value is equal to front node
	def count_and_delete(self) :
		key = self.head.data
		# Define some auxiliary variables
		current = self.head
		auxiliary = None
		back = None
		counter = 0
		# iterating linked list elements
		while (current != None) :
			if (current.data == key) :
				# When get delete node node
				auxiliary = current
				# node counter
				counter = counter + 1
			else :
				back = current
			
			# visit to next node
			current = current.next
			if (auxiliary != None) :
				# When Deleted node exists
				if (self.head == auxiliary) :
					#  When delete first node
					#  head visit to next node
					self.head = current
				else :
					#  Deleted node are exist in intermediate or last position of linked list
					#  Before delete node, there left node is connecting to next upcoming node
					back.next = current
				
				# unlink deleted node 
				auxiliary.next = None
				# free node
				auxiliary = None
			
		
		return counter
	
	def sort_by_frequency(self) :
		if (self.head == None) :
			print("\n Empty linked List", end = "")
		else :
			collection = None
			temp = None
			counter = 0
			key = 0
			current = self.head
			# Set last node to null
			self.tail = None
			# Count node frequency and arrange in sorted order
			while (current != None) :
				key = current.data
				counter = self.count_and_delete()
				collection = self.add_frequency(collection, key, counter)
				current = self.head
			
			#  Add node in linked list by node frequency
			while (collection != None) :
				counter = collection.counter
				key = collection.key
				while (counter > 0) :
					self.add_node(key)
					counter -= 1
				
				temp = collection
				# visit to next node
				collection = collection.next
				# Free node
				temp.next = None
				temp = None
			
		
	

def main() :
	obj = MyLinkedList()
	#  Add linked list node
	obj.add_node(2)
	obj.add_node(6)
	obj.add_node(7)
	obj.add_node(6)
	obj.add_node(3)
	obj.add_node(6)
	obj.add_node(2)
	obj.add_node(3)
	obj.add_node(1)
	obj.add_node(7)
	obj.add_node(3)
	obj.add_node(6)
	obj.add_node(7)
	obj.add_node(1)
	obj.add_node(5)
	obj.add_node(6)
	obj.add_node(9)
	obj.add_node(3)
	print("Before sort by frequency\n", end = "")
	#  2 → 6 → 7 → 6 → 3 → 6 → 2 → 3 → 1 → 7 → 3 → 6 → 7 → 1 → 5 → 6 → 9 → 3 → NULL
	obj.display()
	obj.sort_by_frequency()
	print("Before sort by frequency\n", end = "")
	# 9 → 5 → 1 → 1 → 2 → 2 → 7 → 7 → 7 → 3 → 3 → 3 → 3 → 6 → 6 → 6 → 6 → 6 → NULL
	obj.display()

if __name__ == "__main__": main()

Output

Before sort by frequency
Linked List :   2 →  6 →  7 →  6 →  3 →  6 →  2 →  3 →  1 →  7 →  3 →  6 →  7 →  1 →  5 →  6 →  9 →  3 → NULL
Before sort by frequency
Linked List :   9 →  5 →  1 →  1 →  2 →  2 →  7 →  7 →  7 →  3 →  3 →  3 →  3 →  6 →  6 →  6 →  6 →  6 → NULL
#  Ruby Program
#  Sort the linked list elements by node frequency

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

	# Define the accessor and reader of class Frequency  
	attr_reader :key, :counter, :next
	attr_accessor :key, :counter, :next


	
	def initialize(key, size)
	
		# Set node value
		self.key = key
		self.counter = size
		self.next = nil
	end
end
class MyLinkedList 

	# Define the accessor and reader of class MyLinkedList  
	attr_reader :head, :tail
	attr_accessor :head, :tail


	
	# Class constructor
	def initialize()
	
		self.head = nil
		self.tail = nil
	end
	# insert node at last of linke list
	def add_node(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("Linked List : ")
		# iterating linked list elements
		while (temp != nil)
		
			if (temp != self.head)
			
				print(" →")
			end
			print(" ", temp.data)
			# visit to next node
			temp = temp.next
		end
		print(" → NULL\n")
	end
	def add_frequency(collection, key, counter)
	
		element = Frequency.new(key, counter)
		if (element == nil)
		
			print("Memory overflow\n")
		else
		
			if (collection == nil)
			
				return element
			elsif(collection.counter >= counter)
			
				# When need to add node at beginning
				element.next = collection
				return element
			else
			
				# Sorted add new node
				temp = collection
				while (temp != nil && temp.next != nil && temp.next.counter < counter)
				
					# visit to next node
					temp = temp.next
				end
				element.next = temp.next
				# add element into given collection
				temp.next = element
			end
		end
		return collection
	end
	# Count and delete node which value is equal to front node
	def count_and_delete()
	
		key = self.head.data
		# Define some auxiliary variables
		current = self.head
		auxiliary = nil
		back = nil
		counter = 0
		# iterating linked list elements
		while (current != nil)
		
			if (current.data == key)
			
				# When get delete node node
				auxiliary = current
				# node counter
				counter = counter + 1
			else
			
				back = current
			end
			# visit to next node
			current = current.next
			if (auxiliary != nil)
			
				# When Deleted node exists
				if (self.head == auxiliary)
				
					#  When delete first node
					#  head visit to next node
					self.head = current
				else
				
					#  Deleted node are exist in intermediate or last position of linked list
					#  Before delete node, there left node is connecting to next upcoming node
					back.next = current
				end
				# unlink deleted node 
				auxiliary.next = nil
				# free node
				auxiliary = nil
			end
		end
		return counter
	end
	def sort_by_frequency()
	
		if (self.head == nil)
		
			print("\n Empty linked List")
		else
		
			collection = nil
			temp = nil
			counter = 0
			key = 0
			current = self.head
			# Set last node to null
			self.tail = nil
			# Count node frequency and arrange in sorted order
			while (current != nil)
			
				key = current.data
				counter = self.count_and_delete()
				collection = self.add_frequency(collection, key, counter)
				current = self.head
			end
			#  Add node in linked list by node frequency
			while (collection != nil)
			
				counter = collection.counter
				key = collection.key
				while (counter > 0)
				
					self.add_node(key)
					counter -= 1
				end
				temp = collection
				# visit to next node
				collection = collection.next
				# Free node
				temp.next = nil
				temp = nil
			end
		end
	end
end
def main()

	obj = MyLinkedList.new()
	#  Add linked list node
	obj.add_node(2)
	obj.add_node(6)
	obj.add_node(7)
	obj.add_node(6)
	obj.add_node(3)
	obj.add_node(6)
	obj.add_node(2)
	obj.add_node(3)
	obj.add_node(1)
	obj.add_node(7)
	obj.add_node(3)
	obj.add_node(6)
	obj.add_node(7)
	obj.add_node(1)
	obj.add_node(5)
	obj.add_node(6)
	obj.add_node(9)
	obj.add_node(3)
	print("Before sort by frequency\n")
	#  2 → 6 → 7 → 6 → 3 → 6 → 2 → 3 → 1 → 7 → 3 → 6 → 7 → 1 → 5 → 6 → 9 → 3 → NULL
	obj.display()
	obj.sort_by_frequency()
	print("Before sort by frequency\n")
	# 9 → 5 → 1 → 1 → 2 → 2 → 7 → 7 → 7 → 3 → 3 → 3 → 3 → 6 → 6 → 6 → 6 → 6 → NULL
	obj.display()
end
main()

Output

Before sort by frequency
Linked List :  2 → 6 → 7 → 6 → 3 → 6 → 2 → 3 → 1 → 7 → 3 → 6 → 7 → 1 → 5 → 6 → 9 → 3 → NULL
Before sort by frequency
Linked List :  9 → 5 → 1 → 1 → 2 → 2 → 7 → 7 → 7 → 3 → 3 → 3 → 3 → 6 → 6 → 6 → 6 → 6 → NULL
// Scala Program
// Sort the linked list elements by node frequency

//Node of LinkedList
class Node(var data: Int,
	var next: Node)
{
	def this(data: Int)
	{
		this(data, null);
	}
}
class Frequency(var key: Int,
	var counter: Int,
		var next: Frequency)
{
	def this(key: Int, size: Int)
	{
		this(key, size, null);
	}
}
class MyLinkedList(var head: Node,
	var tail: Node)
{
	//Class constructor
	def this()
	{
		this(null, null);
	}
	//insert node at last of linke list
	def add_node(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("Linked List : ");
		//iterating linked list elements
		while (temp != null)
		{
			if (temp != this.head)
			{
				print(" →");
			}
			print(" " + temp.data);
			//visit to next node
			temp = temp.next;
		}
		print(" → NULL\n");
	}
	def add_frequency(collection: Frequency, key: Int, counter: Int): Frequency = {
		var element: Frequency = new Frequency(key, counter);
		if (element == null)
		{
			print("Memory overflow\n");
		}
		else
		{
			if (collection == null)
			{
				return element;
			}
			else if (collection.counter >= counter)
			{
				//When need to add node at beginning
				element.next = collection;
				return element;
			}
			else
			{
				//Sorted add new node
				var temp: Frequency = collection;
				while (temp != null && temp.next != null && temp.next.counter < counter)
				{
					//visit to next node
					temp = temp.next;
				}
				element.next = temp.next;
				//add element into given collection
				temp.next = element;
			}
		}
		return collection;
	}
	//Count and delete node which value is equal to front node
	def count_and_delete(): Int = {
		var key: Int = this.head.data;
		//Define some auxiliary variables
		var current: Node = this.head;
		var auxiliary: Node = null;
		var back: Node = null;
		var counter: Int = 0;
		//iterating linked list elements
		while (current != null)
		{
			if (current.data == key)
			{
				//When get delete node node
				auxiliary = current;
				//node counter
				counter = counter + 1;
			}
			else
			{
				back = current;
			}
			//visit to next node
			current = current.next;
			if (auxiliary != null)
			{
				//When Deleted node exists
				if (this.head == auxiliary)
				{
					// When delete first node
					// head visit to next node
					this.head = current;
				}
				else
				{
					// Deleted node are exist in intermediate or last position of linked list
					// Before delete node, there left node is connecting to next upcoming node
					back.next = current;
				}
				//unlink deleted node 
				auxiliary.next = null;
				//free node
				auxiliary = null;
			}
		}
		return counter;
	}
	def sort_by_frequency(): Unit = {
		if (this.head == null)
		{
			print("\n Empty linked List");
		}
		else
		{
			var collection: Frequency = null;
			var temp: Frequency = null;
			var counter: Int = 0;
			var key: Int = 0;
			var current: Node = this.head;
			//Set last node to null
			this.tail = null;
			//Count node frequency and arrange in sorted order
			while (current != null)
			{
				key = current.data;
				counter = count_and_delete();
				collection = add_frequency(collection, key, counter);
				current = this.head;
			}
			// Add node in linked list by node frequency
			while (collection != null)
			{
				counter = collection.counter;
				key = collection.key;
				while (counter > 0)
				{
					this.add_node(key);
					counter -= 1;
				}
				temp = collection;
				//visit to next node
				collection = collection.next;
				//Free node
				temp.next = null;
				temp = null;
			}
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var obj: MyLinkedList = new MyLinkedList();
		// Add linked list node
		obj.add_node(2);
		obj.add_node(6);
		obj.add_node(7);
		obj.add_node(6);
		obj.add_node(3);
		obj.add_node(6);
		obj.add_node(2);
		obj.add_node(3);
		obj.add_node(1);
		obj.add_node(7);
		obj.add_node(3);
		obj.add_node(6);
		obj.add_node(7);
		obj.add_node(1);
		obj.add_node(5);
		obj.add_node(6);
		obj.add_node(9);
		obj.add_node(3);
		print("Before sort by frequency\n");
		// 2 → 6 → 7 → 6 → 3 → 6 → 2 → 3 → 1 → 7 → 3 → 6 → 7 → 1 → 5 → 6 → 9 → 3 → NULL
		obj.display();
		obj.sort_by_frequency();
		print("Before sort by frequency\n");
		//9 → 5 → 1 → 1 → 2 → 2 → 7 → 7 → 7 → 3 → 3 → 3 → 3 → 6 → 6 → 6 → 6 → 6 → NULL
		obj.display();
	}
}

Output

Before sort by frequency
Linked List :  2 → 6 → 7 → 6 → 3 → 6 → 2 → 3 → 1 → 7 → 3 → 6 → 7 → 1 → 5 → 6 → 9 → 3 → NULL
Before sort by frequency
Linked List :  9 → 5 → 1 → 1 → 2 → 2 → 7 → 7 → 7 → 3 → 3 → 3 → 3 → 6 → 6 → 6 → 6 → 6 → NULL
// Swift 4 Program
// Sort the linked list elements by node frequency

//Node of LinkedList
class Node
{
	var data: Int;
	var next: Node? ;
	init(_ data: Int)
	{
		//Set node value
		self.data = data;
		self.next = nil;
	}
}
class Frequency
{
	var key: Int;
	var counter: Int;
	var next: Frequency? ;
	init(_ key: Int, _ size: Int)
	{
		//Set node value
		self.key = key;
		self.counter = size;
		self.next = nil;
	}
}
class MyLinkedList
{
	var head: Node? ;
	var tail: Node? ;
	//Class constructor
	init()
	{
		self.head = nil;
		self.tail = nil;
	}
	//insert node at last of linke list
	func add_node(_ 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("Linked List : ", terminator: "");
		//iterating linked list elements
		while (temp != nil)
		{

			print(temp!.data,"→ " ,terminator: "");
			//visit to next node
			temp = temp!.next;
		}
		print(" NULL\n", terminator: "");
	}
	func add_frequency(_ collection: Frequency? , _ key : Int, _ counter: Int) -> Frequency?
	{
		let element: Frequency? = Frequency(key, counter);
		if (element == nil)
		{
			print("Memory overflow\n", terminator: "");
		}
		else
		{
			if (collection == nil)
			{
				return element;
			}
			else if (collection!.counter >= counter)
			{
				//When need to add node at beginning
				element!.next = collection;
				return element;
			}
			else
			{
				//Sorted add new node
				var temp: Frequency? = collection;
				while (temp != nil && temp!.next != nil && temp!.next!.counter < counter)
				{
					//visit to next node
					temp = temp!.next;
				}
				element!.next = temp!.next;
				//add element into given collection
				temp!.next = element;
			}
		}
		return collection;
	}
	//Count and delete node which value is equal to front node
	func count_and_delete() -> Int
	{
		let key: Int = self.head!.data;
		//Define some auxiliary variables
		var current: Node? = self.head;
		var auxiliary: Node? = nil;
		var back: Node? = nil;
		var counter: Int = 0;
		//iterating linked list elements
		while (current != nil)
		{
			if (current!.data == key)
			{
				//When get delete node node
				auxiliary = current;
				//node counter
				counter = counter + 1;
			}
			else
			{
				back = current;
			}
			//visit to next node
			current = current!.next;
			if (auxiliary != nil)
			{
				//When Deleted node exists
				if (self.head === auxiliary)
				{
					// When delete first node
					// head visit to next node
					self.head = current;
				}
				else
				{
					// Deleted node are exist in intermediate or last position of linked list
					// Before delete node, there left node is connecting to next upcoming node
					back!.next = current;
				}
				//unlink deleted node 
				auxiliary!.next = nil;
				//free node
				auxiliary = nil;
			}
		}
		return counter;
	}
	func sort_by_frequency()
	{
		if (self.head == nil)
		{
			print("\n Empty linked List", terminator: "");
		}
		else
		{
			var collection: Frequency? = nil;
			var temp: Frequency? = nil;
			var counter: Int = 0;
			var key: Int = 0;
			var current: Node? = self.head;
			//Set last node to null
			self.tail = nil;
			//Count node frequency and arrange in sorted order
			while (current != nil)
			{
				key = current!.data;
				counter = self.count_and_delete();
				collection = self.add_frequency(collection, key, counter);
				current = self.head;
			}
			// Add node in linked list by node frequency
			while (collection != nil)
			{
				counter = collection!.counter;
				key = collection!.key;
				while (counter > 0)
				{
					self.add_node(key);
					counter -= 1;
				}
				temp = collection;
				//visit to next node
				collection = collection!.next;
				//Free node
				temp!.next = nil;
				temp = nil;
			}
		}
	}
}
func main()
{
	let obj: MyLinkedList = MyLinkedList();
	// Add linked list node
	obj.add_node(2);
	obj.add_node(6);
	obj.add_node(7);
	obj.add_node(6);
	obj.add_node(3);
	obj.add_node(6);
	obj.add_node(2);
	obj.add_node(3);
	obj.add_node(1);
	obj.add_node(7);
	obj.add_node(3);
	obj.add_node(6);
	obj.add_node(7);
	obj.add_node(1);
	obj.add_node(5);
	obj.add_node(6);
	obj.add_node(9);
	obj.add_node(3);
	print("Before sort by frequency\n", terminator: "");
	// 2 → 6 → 7 → 6 → 3 → 6 → 2 → 3 → 1 → 7 → 3 → 6 → 7 → 1 → 5 → 6 → 9 → 3 → NULL
	obj.display();
	obj.sort_by_frequency();
	print("Before sort by frequency\n", terminator: "");
	//9 → 5 → 1 → 1 → 2 → 2 → 7 → 7 → 7 → 3 → 3 → 3 → 3 → 6 → 6 → 6 → 6 → 6 → NULL
	obj.display();
}
main();

Output

Before sort by frequency
Linked List : 2 → 6 → 7 → 6 → 3 → 6 → 2 → 3 → 1 → 7 → 3 → 6 → 7 → 1 → 5 → 6 → 9 → 3 →  NULL
Before sort by frequency
Linked List : 9 → 5 → 1 → 1 → 2 → 2 → 7 → 7 → 7 → 3 → 3 → 3 → 3 → 6 → 6 → 6 → 6 → 6 →  NULL


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







© 2021, kalkicode.com, All rights reserved