Sort a linked list of 0s, 1s, and 2s by changing links

Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Proper understanding of concepts based on Linked Lists can give you an edge in a coding interview.

Problem Statement

In this problem, we are given a linked list containing 0s, 1s, and 2s, and we are required to sort this linked list.

Example

Input:

Output:

Problem Statement Understanding

Let’s learn programming languages online and try to understand

Suppose we are given a linked list 1 → 2 → 0 → 1 → 0 → NULL, now the problem is demanding that we have to sort the linked list such that our original linked list after sorting should look like:
Final resultant linked list after sorting:- 0 → 0 → 1 → 1 → 2 → NULL

Explanation: So basically we have to sort the linked list such that in final sorted linked list 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.

Say if the input linked list is

now in this case after sorting the input linked list our final linked list will look like:
Final resultant linked list after sorting:-

So now I think from the above examples it is clear what the problem is demanding.

Let’s think how we can approach this problem.

Approach 1

As we can see in the problem that our linked list only contains nodes with values 0, 1, and 2, so one simple solution will be to count the number of 0's, 1's, and 2's.

• After counting the number of 0's, 1's, and 2's, fill the first P (where P is count of 0's) nodes with 0, then next Q (where Q is count of 1's) nodes with 1 and last R (where R is count of 2's) nodes with 2.

• After filling the nodes with 0's, 1's, and 2's, our final linked list will be sorted, and we will get our desired result.

But there is one problem, that this solution does not work when these values have associated data with them.

• For example, If these three 0's, 1's, and 2's represent three different colors and with these colors different types of objects have been associated and have to sort the objects based on colors.

So now we will see how can we solve this problem and finally sort the list.

Approach 2

The above problem could be solved by changing the links:

• If we can change the links of nodes such that all the nodes having value of 0 gets together and forms a separate linked list containing all the nodes with value 0. Similarly, the nodes with value 1 and 2 also get together and form their separate linked list.
• After separate linked list for 0's, 1's, and 2's have been formed:
  1) We will make the head of linked list containing 0's as the head of the final sorted linked list.
  2) We will make the tail of linked list of 0's point to the head of linked list of 1's and the tail of linked list of 1's point to the head of linked list of 2's.
  3) Also, we will make tail of linked list of 2's point to NULL.
• Finally, we can return our final sorted linked list by returning the head of linked list of 0's.

Algorithm

• Traverse through the list one by one.
• Maintain three pointers designated ptr0, ptr1, and ptr2 that refer to the current ending nodes of linked lists with 0, 1, and 2 elements, respectively.
• We append each explored Node to the end of its associated list:
  1) Node with value 0 will be appended to the end of linked list of 0's.
  2) Node with value 1 will be appended to end of linked list of 1's.
  3) Node with value 2 will be appended to the end of linked lists of 2's.
• Finally, we join the three lists together. For joining the three lists together we will utilize three dummy pointers temp0, temp1, and temp2 that act as dummy headers for the three lists to avoid multiple null tests.
• Finally, we will return the head of the linked list of 0's.

Dry Run

Code Implementation

#include 
using namespace std;

/* node definition */
struct Node {
    int val;
    struct Node* next;
};

Node* newNode(int val);

// Sorting 0s, 1s and 2s in a linked list
Node* sortingLL(Node* head)
{
    if (!head || !(head->next))
        return head;

// Creating three dummy nodes inorder to point
// to the starting of the 3 lists. 
// Their motive is to help in avoiding null checks.
    Node* temp0 = newNode(0);
    Node* temp1 = newNode(0);
    Node* temp2 = newNode(0);

    // Initialize current pointers
    Node* ptr0 = temp0, *ptr1 = temp1, *ptr2 = temp2;

    // Traversing through the list
    Node* current = head;
    while (current) {
        if (current->val == 0) {
            ptr0->next = current;
            ptr0 = ptr0->next;
            current = current->next;
        } else if (current->val == 1) {
            ptr1->next = current;
            ptr1 = ptr1->next;
            current = current->next;
        } else {
            ptr2->next = current;
            ptr2 = ptr2->next;
            current = current->next;
        }
    }

    // connect the 2 linked lists.
    ptr0->next = (temp1->next)
    ? (temp1->next) : (temp2->next);
    ptr1->next = temp2->next;
    ptr2->next = NULL;

    // Updating the head
    head = temp0->next;

    // Deletion of dummy nodes
    delete temp0;
    delete temp1;
    delete temp2;

    return head;
}

// Creating and returning a node.
Node* newNode(int val)
{
    Node* newNode = new Node;
    newNode->val = val;
    newNode->next = NULL;
}

// Function to display the Linked List
void displayList(struct Node* node)
{
    while (node != NULL) {
        cout<val<<” “;
        node = node->next;
    }
    cout<next = newNode(2);
    head->next->next = newNode(0);
    head->next->next->next = newNode(1);
     head->next->next->next->next = newNode(0);

    cout<<"Original Linked List:”<

						 

Output:

Original Linked List:
1 2 0 1 0
Sorted Linked List:
0 0 1 1 2

Time Complexity: O(n), where n is the number of nodes in the linked list.

In this article, we have tried to explain the most efficient algorithm for sorting a linked list of 0s, 1s, and 2s by changing links. This problem is interesting as well as important from the interview’s point of view. 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.