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.

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

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.

//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
void insert(struct Node**head,int value){
  //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;
    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 element of Node
void display(struct Node*temp){
  
  if(temp==NULL){
    printf("Empty linked list");
  }
  while(temp!=NULL){
    printf("%d  ",temp->data);
    temp=temp->next;
  }
}
void segregate(struct Node**head){
  if(*head==NULL){
    printf("\nEmpty Linked List");
  }else{
    struct 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){
      //Assume that linked list is 
      //combination of 0s,1s and 2s
      //otherwise there are possible to not 
      //get original linked list
      printf("\n Linked list not combination of 0,1,2");
    }else{
      *head=zero;
      //combine linked list
      zero=lastNode(zero);
        zero->next=one;
        one=lastNode(one);
        one->next=two;
    }
  }
}
struct Node* lastNode(struct Node*temp){
  //return address of last node
  while(temp->next!=NULL){
    temp=temp->next;
  }
  return temp;
}

int main(){  
  //create node pointer

  struct Node*head=NULL;
  //insert element of linked list
  insert(&head,1);
  insert(&head,2);
  insert(&head,1);
  insert(&head,0);
  insert(&head,1);
  insert(&head,0);
  printf("Before Sort :");
  //display all node
  display(head);
  segregate(&head);
  printf("\nAfter Sort :");
  //display all node
  display(head);
}

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;
};
class LinkedList{
  Node*head;
  public:
    LinkedList();
    void insert(int);
    void display();
    void segregate();
    Node* lastNode(struct Node*);
};
LinkedList::LinkedList(){
  head=NULL;
}
//insert Node element
void LinkedList::insert(int value){
    //Create dynamic node
  struct Node*node=new Node;
  if(node==NULL){
    cout<<"Memory overflow\n";
  }else{
    node->data=value;
    node->next=NULL;
    if(head==NULL){
      //base condition
      head=node;
    }else{
      Node*temp=head;
      while(temp->next!=NULL){
        temp=temp->next;
      }
      //add newly node at last
      temp->next=node;
    }
  }
}
//display element of Node
void LinkedList:: display(){
  if(head==NULL){
    cout<<"Empty linked list";
  }
  struct Node*temp=head;
  while(temp!=NULL){
    cout<<temp->data<<" ";
    temp=temp->next;
  }
}
Node* LinkedList:: lastNode(struct Node*temp){
  //return address of last node
  while(temp->next!=NULL){
    temp=temp->next;
  }
  return temp;
}

//sort 0s 1s 2s
void LinkedList::segregate(){
  if(head==NULL){
    cout<<"\nEmpty Linked List";
  }else{
    struct 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){
      //Assume that linked list is 
      //combination of 0s,1s and 2s
      //otherwise there are possible to not 
      //get original linked list
      cout<<"\n Linked list not combination of 0,1,2";
    }else{
      head=zero;
      //combine linked list
      zero=lastNode(zero);
        zero->next=one;
        one=lastNode(one);
        one->next=two;
    }
  }
}
int main(){
  //create node pointer
  struct Node*head=NULL;
  //create object
  LinkedList obj;
  //insert element of linked list
  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;
  }
}

public class LinkedList {

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

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

  }
  public Node lastNode(Node temp) {
    //return address of last node
    while (temp.next != null) {
      temp = temp.next;
    }
    return temp;
  }

  //sort 0s,1s, and 2s  
  public void segregate() {
    if (head == null) {
      System.out.println("\nEmpty Linked List");
    } 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) {
        //Assume that linked list is 
        //combination of 0s,1s and 2s
        //otherwise there are possible to not 
        //get original linked list
        System.out.println("\n Linked list not combination of 0,1,2");
      } else {
        head = zero;
        //combine linked list
        zero = lastNode(zero);
        zero.next = one;
        one = lastNode(one);
        one.next = two;
      }
    }
  }

  //Display all Linked List elements
  public void display() {
    if (head != null) {
      System.out.print("Linked List Element :");
      Node temp = head;
      while (temp != null) {
        System.out.print("  " + temp.data);
        temp = temp.next;
      }
    } else {
      System.out.println("Empty Linked list");
    }
  }

  public static void main(String[] args) {

    LinkedList obj = new LinkedList();
    //create object
    //insert element of linked list
    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

#Create Class Linked    
class Linked:
    def __init__(self):
        #Assign default value
        self.head=None

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

    def display(self):
        temp=self.head
        print("Linked List Elements : ")
        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
    
    #segregate linked list nodes
    def segregate(self):
        if(self.head==None):
           print("Empty List") 
        else:
            temp=self.head
            one=None
            two=None
            zero=None
            auxiliary=None
            #Segrate linked list nodes
            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):
                #Assume that linked list is 
                #combination of 0s,1s and 2s
                #otherwise there are possible to not 
                #get original linked list
                print("Linked list not combination of 0,1,2") 
            else:
                self.head=zero
                #combine linked list
                zero=self.lastNode(zero)
                zero.next=one
                one=self.lastNode(one)
                one.next=two

def main():
    #Create Object of class Linked
    obj=Linked()

    #Linked list insertion
    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
Linked List Elements : 
1 0 0 1 2 0 

After Sort List
Linked List Elements : 
0 0 0 1 1 2 

Python : Before sorted,  linked List 0s,1s and 2s python- 0s 1s and 2s  sorted linked list
//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
{
    Node head;
    public Program(){
        head=null;
    }
    //insert node of linked list
    public void insert(int data){
        Node newNode=new Node();
        newNode.data=data;
        newNode.next=null;
        if(head==null) head=newNode;
        else{
            Node temp=head;
            //get last node
            while(temp.next!=null){
                temp=temp.next;
            }
            //add new node
            temp.next=newNode;
        }
    }
    //display linked list nodes value
    public void display(){
        if(head==null){
            Console.Write("Empty List");
        }else{
            Node temp=head;
            while(temp!=null){
                Console.Write("  {0}",temp.data);
                temp=temp.next;
            }
            
        }
    }
    public Node lastNode(Node temp){
      //return address of last node
      while(temp.next!=null){
        temp=temp.next;
      }
      return temp;
    }

  //sort 0s,1s, and 2s  
  public void segregate(){
      if(head==null){
        Console.Write("\nEmpty Linked List");
      }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){
          //Assume that linked list is 
          //combination of 0s,1s and 2s
          //otherwise there are possible to not 
          //get original linked list
          Console.Write("\n Linked list not combination of 0,1,2");
        }else{
          head=zero;
            //combine linked list
            zero=lastNode(zero);
            zero.next=one;
            one=lastNode(one);
            one.next=two;
        }
      }
    }
    static void Main()
    {
        Program obj=new Program();
        //insert element of linked list
        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;
    }
}
class LinkedList{

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

    //sort 0s 1s 2s
    function segregate(){
      if($this->head==NULL){
        echo "<br>Empty Linked List";
      }else{
        $temp=$this->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){
          //Assume that linked list is 
          //combination of 0s,1s and 2s
          //otherwise there are possible to not 
          //get original linked list
          echo "<br> Linked list not combination of 0,1,2";
        }else{
          $this->head=$zero;
          //combine linked list
          $zero=$this->lastNode($zero);
          $zero->next=$one;
          $one=$this->lastNode($one);
          $one->next=$two;
        }
      }
    }
    //Display all inserted node in linked list
    function display()
    {
        if($this->head==NULL)
        {
            echo "Empty Linked List";
        }
        else
        {
            $temp=$this->head;
            echo "<br>Linked List :";
            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
  $obj= new LinkedList();

  /*
  *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.

New Comment







© 2021, kalkicode.com, All rights reserved