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.

Before sort 0s,1s,2s After sort 0s,1s,2s

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.

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.



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