Sort a linked list of 0s, 1s and 2s

Assume that linked list is combination of positive integers (0s, 1s and 2s). And our goal is to arrange this linked list in sorted form. This arrangement is based on only three type of integer (0,1 and 2).

Suppose we are inserted the following (1, 2, 1, 0, 1, 0) node in a sequence.

We can solve this problem in many ways.

Method 1: First is very simple use 3 integer variables. And count number of 0s, 1s and 2s in linked list.

After that put the results frequency into actual linked list.

1) Sort a linked list of 0s 1s and 2s by changing data in c 2) Sort a linked list of 0s 1s and 2s by changing data in java 3) Sort a linked list of 0s 1s and 2s by changing data in c++ 4) Sort a linked list of 0s 1s and 2s by changing data in c# 5) Sort a linked list of 0s 1s and 2s by changing data in php 6) Sort a linked list of 0s 1s and 2s by changing data in python 7) Sort a linked list of 0s 1s and 2s by changing data in ruby 8) Sort a linked list of 0s 1s and 2s by changing data in vb.net 9) Sort a linked list of 0s 1s and 2s by changing data in node js 10) Sort a linked list of 0s 1s and 2s by changing data in typescript 11) Sort a linked list of 0s 1s and 2s by changing data in scala 12) Sort a linked list of 0s 1s and 2s by changing data in swift 13) Sort a linked list of 0s 1s and 2s by changing data in kotlin 14) Sort a linked list of 0s 1s and 2s by changing data in golang

This process time complexity is O(n). But note that this approach are loop will execute 2 times. That is not important but assume that linked list nodes are not a single key that is contain group of other information (like name,address, data value and so on). So This method are not sutable in this situation. In this situation consider second approach.

Method 2: In previous methods we are use of three integers to count number of nodes of 0,1 and 2s. In this process we are using of three pointer of that place. when find node value 0 then add this node to first pointer, similar way to do other nodes for used other pointers.

This process is similar to add nodes of beginning of linked list. for example.

1->0->2->0->1->1
pointer p1-> 0->0->NULL
pointer p2-> 1->1->1->NULL
pointer p3-> 2

After that combine all three linked list into one. Note that this process are iterate all elements in 2 times. first is separate node element by p1,p2,p3. and combine that element are needed one more time iteration.

But this process are work on previous situation and as well as in when linked list data field are more than one member are exist. time complexity are same in method 1 and method 2. Here given example of second methods.

Test cases: Before write an algorithm try to consider following test cases and situations.

1) When linked list are empty, Then display proper message like (Given linked list are empty).

2) We are considered that if by mistake linked list are combination of other integer values then resultant of linked list are not contain those extra node. for example.

Linked list: 1->2->0->1->3->2->3->NULL
Result: 0->1->1->2->2->NULL(Discarded others nodes (3 in this case))

3) Suppose linked list is combination 0,1,2 but in case we are not include any one pair of nodes in linked list. then algorithm is work of 2 pair of nodes and similar when not include 2 pair of nodes.

Linked list: 1->0->0->1->NULL
Result: 0->0->1->1->NULL(pair of 2 not exist)
Linked list: 2->2->2->2->NULL
Result: 2->2->2->2->NULL(pair of 0,1 are not exist)
//so on

Note that we are not including last case in code implementation process because we are assume that linked list is combination of (1,2, and 0s) nodes value. Here given code implementation process.

1) Sort a linked list of 0s 1s and 2s by changing links in c 2) Sort a linked list of 0s 1s and 2s by changing links in java 3) Sort a linked list of 0s 1s and 2s by changing links in c++ 4) Sort a linked list of 0s 1s and 2s by changing links in c# 5) Sort a linked list of 0s 1s and 2s by changing links in golang 6) Sort a linked list of 0s 1s and 2s by changing links in php 7) Sort a linked list of 0s 1s and 2s by changing links in python 8) Sort a linked list of 0s 1s and 2s by changing links in ruby 9) Sort a linked list of 0s 1s and 2s by changing links in scala 10) Sort a linked list of 0s 1s and 2s by changing links in swift 11) Sort a linked list of 0s 1s and 2s by changing links in vb.net 12) Sort a linked list of 0s 1s and 2s by changing links in kotlin 13) Sort a linked list of 0s 1s and 2s by changing links in node js 14) Sort a linked list of 0s 1s and 2s by changing links in typescript