Sort a Linked List of 0s,1s, and 2s

Introduction

In this blog, we will discuss a problem that has been frequently asked in interviews based on important data structure i.e. Linked List.

The problem is to sort a linked list of 0s,1s, and 2s. To understand the solution to the problem, we should first understand the concept of a Linked list. 

A linked list is a linear data structure consisting of nodes where each node points to the next node using a pointer. Each node is composed of data and a pointer to the next node.

Structure of a Node in a linked list:

struct Node
{
    int key;
    Node(int x){
        key=x;
        next=NULL;
    }
    struct Node *next;    
};

You can also try this code with Online C++ Compiler

Run Code

To sort a linked list of 0s,1s, and 2s, we need to return the head of the linked list.

To get more information about the linked list, please refer to this: Linked List.

Some Examples

       Sample Input 1:

       Sample Output 1:    

       Sample Input 2:

       Sample Output 2: 

Recommended: Before stepping onto the solution, practice Sort a Linked List of 0s,1s, and 2s on Codetudio.

Approach

1. Create a function sort() that takes the linked list's head as a parameter and then traverses the linked list to count the 0s,1s, and 2s and stores these values in variables. 
2. Let n1 contain the number of ones, n2 have the number of two's, and n3 includes the number of threes. We will fill the list with 0s,1s, and 2s till n1>0, n2>0, and n3>0, respectively.
3. Since the linked list is now sorted, we will return the head of the linked list.

Code In C++

// Sort a Linked List of 0s,1s, and 2s
#include <bits/stdc++.h>
using namespace std;

// Linked list node
struct Node
{
    int val;
    Node(int x)
    {
        val = x; // variable to store value of node
        next = NULL; // pointer to store address of next node
    }
    struct Node *next;
};

// Function to sort a linked list of 0s, 1s and 2s
void sort(Node *head)
{
    int n0 = 0, n1 = 0, n2 = 0; // The variables to store the frequency of 0s, 1s and 2s

    Node *curr = head; // Initializing the curr with head

    //Storing the count of 0,1 and 2 in the respective variables
    while (curr != NULL)
    {
        if (curr->val == 0)
        {
            n0++; // Increasing frequency of 0s
        }
        else if (curr->val == 1)
        {
            n1++; // Increasing frequency of 1s
        }
        else if (curr->val == 2)
        {
            n2++; // Increasing frequency of 2s
        }
        curr = curr->next; // Traversing the linked list till end
    }

    //Since we have to traverse from the head, we are reinitializing the value of curr with head

    curr = head;

    while (curr != NULL)
    {
        if (n0 > 0) // filling the list with 0, till n0 > 0
        {
            curr->val = 0; // changing value of node to 0
            curr = curr->next;
            n0--;
        }
        else if (n1 > 0) // filling the list with 1, till n2 > 0
        {
            curr->val = 1; // changing value of node to 1
            curr = curr->next;
            n1--;
        }
        else if (n2 > 0) // filling the list with 2, till n2 > 0
        {
            curr->val = 2; // changing value of node to 2
            curr = curr->next;
            n2--;
        }
    }
}

// Function to insert a node
Node *insert(Node *x, int y)
{
    Node *temp = new Node(y);
    temp->next = x;
    return temp;
}

// Function to print linked list
void printList(Node *node)
{
    while (node != NULL)
    {
        cout << node->val << " ";
        node = node->next;
    }
    cout << endl;
}

// Driver code
int main()
{
    Node *head = NULL;
    head = insert(head, 0);
    head = insert(head, 1);
    head = insert(head, 0);
    head = insert(head, 2);
    head = insert(head, 0);
    head = insert(head, 1);
    head = insert(head, 1);
    head = insert(head, 1);
    head = insert(head, 2);
    head = insert(head, 2);
    head = insert(head, 0);.
    cout << "Input: ";
    printList(head);

    sort(head);

    cout << "Output: ";
    printList(head);
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Sample Input and Output:

Input:  0 2 2 1 1 1 0 2 0 1 0

Output: 0 0 0 0 1 1 1 1 2 2 2

Complexity Analysis

Time Complexity: O(n) (Worst Case)

Since there are n nodes in the linked list and we are doing traversals of the whole linked list, therefore, the time complexity is O(n).

Space Complexity: O(1) (Worst case)

Since we are not using any data structures other than the linked list given to us, therefore, the space complexity is O(1).