Sort linked list containing 0’s, 1’s and 2’s

Problem: Given a linked list containing 0’s, 1’s and 2’s, sort linked list. Can you do this in a single traversal?

For example:

Input: 0 -> 1 -> 2 -> 2 -> 1 -> 0 -> 0 -> 2 -> 0 -> 1 -> 1 -> 0 -> NULL
Output: 0 -> 0 -> 0 -> 0 -> 0 -> 1 -> 1 -> 1 -> 1 -> 2 -> 2 -> 2 -> NULL

Input: 2 -> 1 -> 2 -> 1 -> 1 -> 2 -> 0 -> 1 -> 0 -> NULL
Output: 0 -> 0 -> 1 -> 1 -> 1 -> 1 -> 2 -> 2 -> 2 -> NULL

Method 1: Simplest method one can com across is counting the frequency of zero, one and two in first traversal and in second traversal updating the values of the nodes of linked list in required order.

void sortLinkedlist(struct Node *head)
{
    /* handling base case */
    if(head == NULL || head->next == NULL)
        return;

    /* count total number of '0', '1' and '2'
       count[0] will store total number of '0's
       count[1] will store total number of '1's
       count[2] will store total number of '2's  */
    int count[3] = {0, 0, 0};

    struct Node *temp = head;

    /* counting the frequencies */
    while (temp)
    {
        count[temp->data] += 1;
        temp = temp->next;
    }

    int i = 0;
    temp = head;

    /* updating the values in required order */
    while(temp)
    {
        if (count[i] == 0)
            ++i;
        else
        {
            temp->data = i;
            count[i]--;
            temp = temp->next;
        }
    }
}

Time Complexity: O(n) and Space Complexity: O(1)

Method 2: The above method is using two traversal. According to our problem statement, can we do it in single traversal? Yes, we can do this in single traversal. Following is the approach:

For each Node in the list:

• If it has 0 
• Move to the Front of list 
• If it has 2 
•  Move to the End of list 
•  If it has 1 Do nothing.

void sortLinkedlist(Node* &head)
{
    /* handling base case */
    if(head == NULL || head->next == NULL)
        return;
    
    /* pointer to last node in the linked list */
    Node *lst = head;
    int totalNodes = 1;
    while(lst->next != NULL)
    {
        lst = lst->next;
        totalNodes++;
    }

    Node *tail = lst;
    Node *ptr = head;
    Node *prev = head;
    for(int i = 0; i < totalNodes; i++)
    {
        Node *curr = temp;
        temp = temp->next;

        if(curr->data == 0)
        {
            /* insert it at head */
            if(prev != curr)
            {
                curr->next = head;
                head = curr;
                prev->next = temp;
            }
        }
        else if(curr->data == 2)
        {
            /* insert it at the end */
            tail->next = curr;
            curr->next = NULL;
            tail = curr;

            /* if first Node */
            if(prev == curr)
                head = prev = temp;
            else
                prev->next = temp;
        }
        else
        {
            if(prev != curr)
                prev = prev->next;
        }
    }
}

Time Complexity: O(n) and Space Complexity: O(1)

Method 3: There is one more method to do this problem in single traversal. The idea is to maintain three pointers zeros, ones and twos. Then, we traverse the list from head to end and move each node to the corresponding list depending on its value. Finally, we combine all three lists at the end and x the head pointer.

void sortLinkedlist(Node* &head)
{
    /* handling base case */
    if (head == NULL || head->next == NULL)
        return;
 
    /* three dummy nodes one each for zeros, one and twos */
    struct Node zeros, ones, twos;

    zeros->next = NULL;
    ones->next = NULL;
    twos->next = NULL;
 
    struct Node *curr = head;
 
    /* travering the list */
    while (curr != NULL)
    {
        if (curr->data == 0)
        {
            zero->next = curr;
            zero = zero->next;
        }
        else if (curr->data == 1)
        {
            one->next = curr;
            one = one->next;
        }
        else
        {
            two->next = curr;
            two = two->next;
        }
        curr = curr->next;
    }
 
    /* combining lists containing 0's, 1's and 2's */
    zero -> next = (ones -> next) ? (ones -> next) : (twos -> next);
    one -> next = twos.next;
    two -> next = NULL;
 
    /* change head to point new head */
    head = zeros->next;
}

Time Complexity: O(n) and Space Complexity: O(1)