Last Updated on March 10, 2022 by Ria Pathak
Introduction
The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.
Problem Statement
In this question, we are given a singly linked list, which only contains 0’s, 1’s and 2’s. We have to sort the given list in non-decreasing order.
Problem Statement Understanding
Let’s try to understand the problem statement with the help of examples.
Suppose the given linked list is: 1 → 1 → 0 → 2 → 2.
- Now, according to the problem statement we have to sort the given linked list such that after sorting the final linked list will look like: 0 → 1 → 1 → 2 → 2.
- So basically, we will have to sort our linked list such that all the nodes with value 0 comes before the nodes with value 1 and all the nodes with value 1 comes before the nodes with value 2.
If the given linked list is: 1 → 0 → 0 → 2 → 2 → 1 → 0 → 2 → 2.
- Then, in this case, our output sorted linked list will be: 0 → 0 → 0 → 1 → 1 → 2 → 2 → 2 → 2.
Some more examples:
Sample Input 1: 2 → 2 → 1 → 0
Sample Output 1: 0 → 1 → 2 → 2
Sample Input 2: 0 → 2 → 1 → 1
Sample Output 2: 0 → 1 → 1 → 2
Sample Input 3: 1 → 1 → 0 → 2 → 2
Sample Output 3: 0 → 1 → 1 → 2 → 2
Now I think from the above examples, the problem statement is clear. So let’s see how we will approach it.
Before moving to the approach section, try to think, how should we approach this problem?
- One simple way is to sort the linked list using any sorting algorithm (choose wisely). It will do our work, but our complexity will be O(nlog(n)), and also we should keep in mind that in our problem there are only three values possible (0, 1 and 2), so we should also utilize this information.
Instead of directly applying sorting on the linked list, try to think of some better way to sort the list. Will it be helpful if we count the number of 0’s, 1’s and 2’s?
- Yes, it will be very helpful. Our approach is going to make use of this count.
Let us have a glance at the approach.
Approach
Our approach is going to be pretty simple.
- We will traverse the list and count the number of 0’s, 1’s and 2’s. Now, how will counting be helpful to us? Well, after counting, let the number of 0’s be x, the number of 1’s be y and the number of 2’s be z.
- Now, with the help of the counts, we will traverse the list again and fill the first x nodes with 0, then next y nodes with 1 and then next z nodes with 2.
- If we notice carefully, this will make our list sorted, as 0’s will come first, then 1’s and finally 2’s. Hence, our objective to sort the linked list.
Algorithm
- Create an array cnt , which will have a size of 3 and all the elements will initially be 0.
- Create a node ptr and point it to the head of the list. This pointer ptr will be used to traverse the list.
- Now, traverse the list and for every node do, cnt [ ptr – > data ] + = 1.
- In the above step, if ptr -> data is 0, then the value at 0th index of the array will increase and hence, the indexes 0, 1 and 2 will contain the number of 0’s, 1’s and 2’s respectively.
- Now, create a variable i and initialize it with 0. This i will be the element that will be inserted in the nodes, i.e., 0, 1 or 2.
- Now, make the ptr point to the head again, as we need to traverse the list again.
- In the loop while traversing:
- if count[i] = 0, we will increment i.
- Else we will make ptr -> data = i and decrement count[i]. What is the significance of this?
- Suppose count[0] is 3. Now, For the first 3 iterations, ptr -> data will be equal to 0.
- As the count[0] is getting decreased in every iteration, after 3 iterations, the count[0] will be 0, so now, we will increment i as now we have to fill the next y (where y is the number of nodes with data 1) nodes with 1. The same process will get repeated with 1’s and 2’s.
- Finally, our list will get sorted.
Dry Run
Code Implementation
#include<stdio.h>
#include<stdlib.h>
/* Link list node */
struct Node
{
int data;
struct Node* next;
};
void sortList(struct Node *head)
{
int count[3] = {0, 0, 0}; // Initialize count of '0', '1' and '2' as 0
struct Node *ptr = head;
while (ptr != NULL)
{
count[ptr->data] += 1;
ptr = ptr->next;
}
int i = 0;
ptr = head;
while (ptr != NULL)
{
if (count[i] == 0)
++i;
else
{
ptr->data = i;
--count[i];
ptr = ptr->next;
}
}
}
void push (struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
void printList(struct Node *node)
{
while (node != NULL)
{
printf("%d ", node->data);
node = node->next;
}
printf("n");
}
int main(void)
{
struct Node *head = NULL;
push(&head, 0);
push(&head, 1);
push(&head, 0);
push(&head, 2);
push(&head, 1);
push(&head, 1);
push(&head, 2);
push(&head, 1);
push(&head, 2);
printf("Linked List Before Sorting\n");
printList(head);
sortList(head);
printf("Linked List After Sorting\n");
printList(head);
return 0;
}
#include <bits stdc++.h="">
using namespace std;
class Node
{
public:
int data;
Node* next;
};
/* We will use this function to sort the linked list containing 0's, 1's and 2's */
void sort(Node *head)
{
int count[3] = {0, 0, 0};
Node *ptr = head;
while (ptr != NULL)
{
count[ptr->data] += 1;
ptr = ptr->next;
}
int i = 0;
ptr = head;
while (ptr != NULL)
{
if (count[i] == 0)
++i;
else
{
ptr->data = i;
--count[i];
ptr = ptr->next;
}
}
}
/* This function is used to insert nodes at head of the linked list */
void push (Node** head, int new_data)
{
Node* new_node = new Node();
new_node->data = new_data;
new_node->next = (*head);
(*head) = new_node;
}
/* This function is used to print the linked list */
void print(Node *node)
{
while (node != NULL)
{
cout << node->data << " ";
node = node->next;
}
cout << endl;
}
int main(void)
{
Node *head = NULL;
push(&head, 2);
push(&head, 2);
push(&head, 0);
push(&head, 1);
push(&head, 1);
cout << "Initial Linked List Before Sorting\n";
print(head);
sort(head);
cout << "Resultant Linked List After Sorting\n";
print(head);
return 0;
}
public class LinkedList
{
Node head;
class Node
{
int data;
Node next;
Node(int d) {data = d; next = null; }
}
/* We will use this function to sort the linked list containing 0's, 1's and 2's */
void sort()
{
int count[] = {0, 0, 0};
Node ptr = head;
while (ptr != null)
{
count[ptr.data]++;
ptr = ptr.next;
}
int i = 0;
ptr = head;
while (ptr != null)
{
if (count[i] == 0)
i++;
else
{
ptr.data= i;
--count[i];
ptr = ptr.next;
}
}
}
/* This function is used to insert nodes at head of the linked list */
public void push(int new_data)
{
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
/* This function is used to print the linked list */
void print()
{
Node temp = head;
while (temp != null)
{
System.out.print(temp.data+" ");
temp = temp.next;
}
System.out.println();
}
public static void main(String args[])
{
LinkedList llist = new LinkedList();
llist.push(2);
llist.push(2);
llist.push(0);
llist.push(1);
llist.push(1);
System.out.println("Initial Linked List before sorting");
llist.print();
llist.sort();
System.out.println("Resultant Linked List after sorting");
llist.print();
}
}
class LinkedList(object):
def __init__(self):
self.head = None
class Node(object):
def __init__(self, d):
self.data = d
self.next = None
def sortList(self):
count = [0, 0, 0]
ptr = self.head
while ptr != None:
count[ptr.data]+=1
ptr = ptr.next
i = 0
ptr = self.head
while ptr != None:
if count[i] == 0:
i+=1
else:
ptr.data = i
count[i]-=1
ptr = ptr.next
def push(self, new_data):
new_node = self.Node(new_data)
new_node.next = self.head
self.head = new_node
def printList(self):
temp = self.head
while temp != None:
print (str(temp.data),end=" ")
temp = temp.next
print()
llist = LinkedList()
llist.push(2)
llist.push(2)
llist.push(0)
llist.push(1)
llist.push(1)
print ("Linked List before sorting")
llist.printList()
llist.sortList()
print ("Linked List after sorting")
llist.printList()
Output
Initial Linked List before sorting
1 1 0 2 2
Resultant Linked List after sorting
0 1 1 2 2
Time Complexity: O(n), as list traversal is needed.
Space Complexity: O(3), which is almost constant, as an array of size 3 is being made.
So, in this article, we have tried our best to explain how to sort a linked list of 0’s, 1’s and 2’s. You can also sort a linked list of 0’s, 1’s and 2’s by changing links. Check out our article How to sort a linked list of 0s, 1s and 2s by changing links.
This is an important question when it comes to coding interviews.If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.