# 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).

We can solve this problem in many ways.

Method 1: First is very simple use 3 integers and itersal of linked list node are one by one. when node value is one increment first variable value by one . similarly increment other variables when get other nodes.

When iterate all node we are know about how many number of 0's 1's and 2's nodes are exist. After that we are again iterate linked list nodes. Set using of this resulted value set beginning N nodes by 0 , After that N nodes are set by 1, and last pair is contain N nodes of 2s.

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.

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

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

``````//C Program for
//Sort linked list in form of 0s,1s and 2s
#include<stdio.h>
#include <stdlib.h> //for malloc function

//Create structure
struct Node{
int data;
struct Node*next;
};
//function prototype
void insert(struct Node**,int);
void display(struct Node*);
void segregate(struct Node**);
struct Node* lastNode(struct Node*);
//insert Node element
//Create dynamic node
struct Node*node=(struct Node*)malloc(sizeof(struct Node));
if(node==NULL){
printf("Memory overflow\n");
}else{
node->data=value;
node->next=NULL;
}else{
//find last node
while(temp->next!=NULL){
temp=temp->next;
}
temp->next=node;
}
}
}
//Display element of Node
void display(struct Node*temp){

if(temp==NULL){
}
while(temp!=NULL){
printf("%d  ",temp->data);
temp=temp->next;
}
}
}else{
*two=NULL,*zero=NULL,
*auxiliary=NULL;

while(temp!=NULL){
auxiliary=temp->next;
if(temp->data==0){
temp->next=zero;
zero=temp;
}else if(temp->data==1){
temp->next=one;
one=temp;
}else if(temp->data==2){
temp->next=two;
two=temp;
}else{
//invaild data
}
temp=auxiliary;
}
if(zero==NULL||one==NULL||two==NULL){
//combination of 0s,1s and 2s
//otherwise there are possible to not
printf("\n Linked list not combination of 0,1,2");
}else{
zero=lastNode(zero);
zero->next=one;
one=lastNode(one);
one->next=two;
}
}
}
struct Node* lastNode(struct Node*temp){
while(temp->next!=NULL){
temp=temp->next;
}
return temp;
}

int main(){
//create node pointer

printf("Before Sort :");
//display all node
printf("\nAfter Sort :");
//display all node
}``````

#### Output

``````Before Sort :1  2  1  0  1  0
After Sort :0  0  1  1  1  2 ``````
``````//C++ Program
//Sort linked list in form of 0s,1s and 2s
#include<iostream>
using namespace std;

//create structure
struct Node{
int data;
struct Node*next;
};
public:
void insert(int);
void display();
void segregate();
Node* lastNode(struct Node*);
};
}
//insert Node element
//Create dynamic node
struct Node*node=new Node;
if(node==NULL){
cout<<"Memory overflow\n";
}else{
node->data=value;
node->next=NULL;
//base condition
}else{
while(temp->next!=NULL){
temp=temp->next;
}
temp->next=node;
}
}
}
//display element of Node
}
while(temp!=NULL){
cout<<temp->data<<" ";
temp=temp->next;
}
}
while(temp->next!=NULL){
temp=temp->next;
}
return temp;
}

//sort 0s 1s 2s
}else{
*two=NULL,*zero=NULL,
*auxiliary=NULL;

while(temp!=NULL){
auxiliary=temp->next;
if(temp->data==0){
temp->next=zero;
zero=temp;
}else if(temp->data==1){
temp->next=one;
one=temp;
}else if(temp->data==2){
temp->next=two;
two=temp;
}else{
//invaild data
}
temp=auxiliary;
}
if(zero==NULL||one==NULL||two==NULL){
//combination of 0s,1s and 2s
//otherwise there are possible to not
cout<<"\n Linked list not combination of 0,1,2";
}else{
zero=lastNode(zero);
zero->next=one;
one=lastNode(one);
one->next=two;
}
}
}
int main(){
//create node pointer
//create object
obj.insert(1);
obj.insert(2);
obj.insert(1);
obj.insert(0);
obj.insert(1);
obj.insert(0);
cout<<"Before Sort :";
//display all node
obj.display();
obj.segregate();
cout<<"\nAfter Sort :";
//display all node
obj.display();
}``````

#### Output

``````Before Sort :1 2 1 0 1 0
After Sort :0 0 1 1 1 2``````
``````//Java Program
//Sort linked list in form of 0s,1s and 2s
class Node {
public int data;
public Node next;
public Node(int value) {
data = value;
next = null;
}
}

//Class constructors
}
//insert element
public void insert(int value) {
//Create  node
Node node = new Node(value);

else {
//find last node
while (temp.next != null) {
temp = temp.next;
}
temp.next = node;
}

}
public Node lastNode(Node temp) {
while (temp.next != null) {
temp = temp.next;
}
return temp;
}

//sort 0s,1s, and 2s
public void segregate() {
} else {
Node temp = head, one = null, two = null, zero = null, auxiliary = null;

while (temp != null) {
auxiliary = temp.next;
if (temp.data == 0) {
temp.next = zero;
zero = temp;
} else if (temp.data == 1) {
temp.next = one;
one = temp;
} else if (temp.data == 2) {
temp.next = two;
two = temp;
} else {
//invaild data
}
temp = auxiliary;
}
if (zero == null || one == null || two == null) {
//combination of 0s,1s and 2s
//otherwise there are possible to not
System.out.println("\n Linked list not combination of 0,1,2");
} else {
zero = lastNode(zero);
zero.next = one;
one = lastNode(one);
one.next = two;
}
}
}

public void display() {
while (temp != null) {
System.out.print("  " + temp.data);
temp = temp.next;
}
} else {
}
}

public static void main(String[] args) {

//create object
obj.insert(1);
obj.insert(2);
obj.insert(1);
obj.insert(0);
obj.insert(1);
obj.insert(0);
System.out.println("Before Sort :");
//display all node
obj.display();
obj.segregate();
System.out.println("\nAfter Sort :");
//display all node
obj.display();
}
}``````

#### Output

``````Before Sort :
Linked List Element :  1  2  1  0  1  0
After Sort :
Linked List Element :  0  0  1  1  1  2``````
``````#Python Program
#Sort linked list in form of 0s,1s and 2s
class Node:
def __init__(self,data):
self.data=data
self.next=None

def __init__(self):
#Assign default value

#insert new node to linked list
def insert(self,data):
node=Node(data)
node.next=None
else:
while temp.next!=None:
temp=temp.next
temp.next=node

def display(self):
while(temp!=None):
print(temp.data,end=" ")
temp=temp.next
print("\n")

#return last node
def lastNode(self,temp):
while temp.next!=None:
temp=temp.next

return temp

def segregate(self):
print("Empty List")
else:
one=None
two=None
zero=None
auxiliary=None
while(temp!=None):
auxiliary=temp.next
if(temp.data==0):
temp.next=zero
zero=temp
elif(temp.data==1):
temp.next=one
one=temp
elif(temp.data==2):
temp.next=two
two=temp
else:
print("Invalid node not conside",temp.data)
temp=auxiliary
#check valid node
if(zero==None or one==None or two==None):
#combination of 0s,1s and 2s
#otherwise there are possible to not
print("Linked list not combination of 0,1,2")
else:
zero=self.lastNode(zero)
zero.next=one
one=self.lastNode(one)
one.next=two

def main():

obj.insert(1)
obj.insert(0)
obj.insert(0)
obj.insert(1)
obj.insert(2)
obj.insert(0)

print("Before Sort List")
obj.display()
print("After Sort List")
obj.segregate()
obj.display()

if __name__=="__main__":
main()``````

#### Output

``````Before Sort List
1 0 0 1 2 0

After Sort List
0 0 0 1 1 2

``````
``````//C# Program
//Sort linked list in form of 0s,1s and 2s
using System;
//node class
public class Node{
public  int data;
public  Node next;
}
class Program
{
public Program(){
}
public void insert(int data){
Node newNode=new Node();
newNode.data=data;
newNode.next=null;
else{
//get last node
while(temp.next!=null){
temp=temp.next;
}
temp.next=newNode;
}
}
public void display(){
Console.Write("Empty List");
}else{
while(temp!=null){
Console.Write("  {0}",temp.data);
temp=temp.next;
}

}
}
public Node lastNode(Node temp){
while(temp.next!=null){
temp=temp.next;
}
return temp;
}

//sort 0s,1s, and 2s
public void segregate(){
}else{

while(temp!=null){
auxiliary=temp.next;
if(temp.data==0){
temp.next=zero;
zero=temp;
}else if(temp.data==1){
temp.next=one;
one=temp;
}else if(temp.data==2){
temp.next=two;
two=temp;
}else{
//invaild data
}
temp=auxiliary;
}
if(zero==null||one==null||two==null){
//combination of 0s,1s and 2s
//otherwise there are possible to not
Console.Write("\n Linked list not combination of 0,1,2");
}else{
zero=lastNode(zero);
zero.next=one;
one=lastNode(one);
one.next=two;
}
}
}
static void Main()
{
Program obj=new Program();
obj.insert(1);
obj.insert(2);
obj.insert(1);
obj.insert(0);
obj.insert(1);
obj.insert(0);
Console.Write("Before Sort :");
//display all node
obj.display();
obj.segregate();
Console.Write("\nAfter Sort :");
//display all node
obj.display();
}
}``````

#### Output

``````Before Sort :  1  2  1  0  1  0
After Sort :  0  0  1  1  1  2``````
``````<?php
//Php program
//Sort linked list in form of 0s,1s and 2st
class Node
{
public \$data;
public \$next;
function __construct(\$data)
{
\$this->data = \$data;
\$this->next = NULL;
}
}

function __construct()
{
}
/*
* Append the Given data value at end of linked list
* Fun : insert
* Parm: data value
*@return None
*/
function insert(\$data)
{
\$newNode=new Node(\$data);
{
}else{
//find last node of linked list
while(\$temp->next!=NULL){
\$temp=\$temp->next;
}
\$temp->next=\$newNode;
}
}
function lastNode(\$temp){
while(\$temp->next!=NULL){
\$temp=\$temp->next;
}
return \$temp;
}

//sort 0s 1s 2s
function segregate(){
}else{
\$one=NULL;
\$two=NULL;
\$zero=NULL;
\$auxiliary=NULL;

while(\$temp!=NULL){
\$auxiliary=\$temp->next;
if(\$temp->data==0){
\$temp->next=\$zero;
\$zero=\$temp;
}else if(\$temp->data==1){
\$temp->next=\$one;
\$one=\$temp;
}else if(\$temp->data==2){
\$temp->next=\$two;
\$two=\$temp;
}else{
//invaild data
}
\$temp=\$auxiliary;
}
if(\$zero==NULL||\$one==NULL||\$two==NULL){
//combination of 0s,1s and 2s
//otherwise there are possible to not
echo "<br> Linked list not combination of 0,1,2";
}else{
\$zero=\$this->lastNode(\$zero);
\$zero->next=\$one;
\$one=\$this->lastNode(\$one);
\$one->next=\$two;
}
}
}
//Display all inserted node in linked list
function display()
{
{
}
else
{
while(\$temp!=NULL)
{
//display node value
echo "&nbsp;&nbsp;".\$temp->data;
\$temp=\$temp->next; //visit to next node
}
}
}
}
function main(){
//Make a object of LinkedList class

/*
*Insert following nodes in linked list
*/

\$obj->insert(1);
\$obj->insert(2);
\$obj->insert(1);
\$obj->insert(0);
\$obj->insert(1);
\$obj->insert(0);
echo "Before Sort :";
//display all node
\$obj->display();
\$obj->segregate();
echo "<br>After Sort :";
//display all node
\$obj->display();
}
main();
?>``````

#### Output

``````Before Sort :
Linked List :  1  2  1  0  1  0
After Sort :
Linked List :  0  0  1  1  1  2``````

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.