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

Given a Singly linked list with each node containing either 0, 1 or 2. Write code to sort the list.
Input : 1 -> 1 -> 2 -> 0 -> 2 -> 0 -> 1 -> 0
Output : 0 -> 0 -> 0 -> 1 -> 1 -> 1 -> 2 -> 2

Solution:
You can do that in O(n).

Traverse the linked list from the beginning and count the number of 0s, 1s and 2s. (Let the counts be p, q, r)
Now traverse the linked list again and set first p nodes to 0, q nodes to 1 and r nodes to 2.

/* Link list node */
struct node
{
    int data;
    struct node* link;
};

// Function to sort a linked list of 0s, 1s and 2s
void sortList(struct node *start)
{
    int count[3] = {0, 0, 0};  
    struct node *ptr = start;

    /* 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  */
    while (ptr)
    {
        count[ptr->data] += 1;
        ptr = ptr->link;
    }

    int i = 0;
    ptr = start;

    while (ptr)
    {
        if (count[i] == 0)
            ++i;
        else
        {
            ptr->data = i;
            count[i]--;
            ptr = ptr->link;
        }
    }
}

One Thought on “Sort a Linked List of 0s, 1s and 2s

  1. Nancy Goyal on May 7, 2015 at 7:00 pm said:

    The above program will not give the desired output.
    There is a bug in this program. The sortList function should go like this
    void sortList(struct node *start)
    10 {
    11 int count[3] = {0, 0, 0};
    12 struct node *ptr = start;
    13
    14 /* count total number of ’0′, ’1′ and ’2′
    15 * count[0] will store total number of ’0′s
    16 * count[1] will store total number of ’1′s
    17 * count[2] will store total number of ’2′s */
    18 while (ptr)
    19 {
    20 count[ptr->data] += 1;
    21 ptr = ptr->link;
    22 }
    23
    24 int i = 0;
    25 ptr = start;
    26
    27 while (ptr)
    28 {
    29 if (count[i] == 0)
    30 ++i;
    31 //else //This piece of code in else part should execute every iterate
    32 //{
    33 ptr->data = i;
    34 count[i]–;
    35 ptr = ptr->link;
    36 // }
    37 }
    38 }

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Post Navigation