Home » Interview Questions » LinkedList Interview Questions » Sort a linked list with 0s, 1s and 2s

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


()

In the given linked list, which contains only 0s, 1s or 2s. Write a function to sort the linked list.

Example

Time complexity : O(n)

Algorithm

a. Create a count array of size 3,

count[1] stores count of 0
count[1] stores count of 1
count[2] stores count of 2

b. Traverse in the linked list count the number of 0s, 1s and 2s. Let counts be c0, c1 and c2.

c. Traverse the linked list again and fill it with 0s first c0 nodes, 1s with next c1 nodes and last c2 nodes with 2s.

Algorithm working

C++ Program

#include <bits/stdc++.h>

using namespace std;

struct LLNode
{
    int data;
    struct LLNode* next;
};
 
//Function to sort linked list
void SortLL(struct LLNode *head)
{
    //count array to store count of 0s, 1s and 2s
    //temp is pointer to traverse in the array
    int count[3] = {0, 0, 0};
    struct LLNode *temp = head;
    while (temp != NULL)
    {
        count[temp->data] += 1;
        temp = temp->next;
    }
    //Traverse in the array and fill with 0s, 1s and 2s
    //first count[0] places with 0s
    //second count[1] places with 1s
    //last count[2] places with 2s
    int i = 0;
    temp = head;
    while (temp != NULL)
    {
        if (count[i] == 0)
        {
            i = i + 1;
        }
        else
        {
            temp->data = i;
            count[i] = count[i] - 1 ;
            temp = temp->next;
        }
    }
}
 
/* Function to insertAtBeginning a node */
void insertAtBeginning(struct LLNode** head, int dataToBeInserted)
{
    struct LLNode* curr = new LLNode;
    curr->data = dataToBeInserted;
    curr->next = NULL;    
    if(*head == NULL)
            *head=curr; //if this is first node make this as head of list
        
    else
        {
            curr->next=*head; //else make the curr (new) node's next point to head and make this new node a the head
            *head=curr;
        }
        
        //O(1) constant time
}
 
//display linked list
void display(struct LLNode**node)
{
    struct LLNode *temp= *node;
    while(temp!=NULL)
        {
            if(temp->next!=NULL)
            cout<<temp->data<<" ->";
            else
            cout<<temp->data;
            
            temp=temp->next; //move to next node
        }
        //O(number of nodes)
    cout<<endl;
}
 
//Main function
int main(void)
{
    struct LLNode *head = NULL;
    insertAtBeginning(&head, 0);
    insertAtBeginning(&head, 1);
    insertAtBeginning(&head, 0);
    insertAtBeginning(&head, 2);
    insertAtBeginning(&head, 1);
    insertAtBeginning(&head, 1);
    insertAtBeginning(&head, 2);
    insertAtBeginning(&head, 1);
    insertAtBeginning(&head, 2);
 
    cout<<"Input linked list: ";
    display(&head);
    SortLL(head);
    cout<<"\nOutput linked list after sorting\n";
    display(&head);
    return 0;
}

READ  Add two numbers

 

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions