Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com

Sort linked list of 0s 1s 2s

Easy
0/40
Average time to solve is 10m
profile
Contributed by
245 upvotes
Asked in companies
MakeMyTripInnovaccerIntuit

Problem statement

Given a linked list of 'N' nodes, where each node has an integer value that can be 0, 1, or 2. You need to sort the linked list in non-decreasing order and the return the head of the sorted list.


Example:
Given linked list is 1 -> 0 -> 2 -> 1 -> 2. 
The sorted list for the given linked list will be 0 -> 1 -> 1 -> 2 -> 2.


Detailed explanation ( Input/output format, Notes, Images )
Input Format :
The first line contains an integer 'N', the size of the linked list.
The second line contains 'N' space-separated integers containing 0, 1 and 2 only.


Output Format :
The output contains all the integers in non-decreasing order.


Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Sample Input 1:
7
1 0 2 1 0 2 1


Sample Output 1:
0 0 1 1 1 2 2


Explanation Of Sample Input 1:
Input: 1 -> 0 -> 2 -> 1 -> 0 -> 2 -> 1

Output: 0 -> 0 -> 1 -> 1 -> 1 -> 2 -> 2

Explanation: 
In this example, the original linked list contains two 0s, three 1s, and two 2s. The sorted linked list has all the 0s at the beginning, followed by all the 1s, and finally, all the 2s at the end.


Sample Input 2:
8
2 1 0 2 1 0 0 2


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


Follow Up:
Can you solve this without updating the Nodes of the given linked list?


Constraints :
1 <= N <= 10^3
0 <= data <= 2 

Where 'N' is the length of the linked list.

Time Limit: 1 sec
Hint

Count the number of occurrences, then update the linked list.

Approaches (2)
Updating nodes data

The approach would be counting the number of occurrences of 0, 1, and 2. Then updating the data of the linked list in sorted order.

 

  • Make 3 different variables to store the count of 0, 1 and 2.
  • Traverse over the given linked list and increase the count of respective variables.
  • Now traverse the linked list again and update data of first count(0) number of nodes to 0, then next count(1) number of nodes to 1 and the remaining count(2) number of nodes to 2.
Time Complexity

O(N), where N is the number of nodes in the linked list.

 

In the worst case, we will be traversing the linked list twice. Hence the overall time complexity is O(N).

Space Complexity

O(1).

 

In the worst case, we are using constant extra space. Hence the overall space complexity is O(1).

Code Solution
(100% EXP penalty)
Sort linked list of 0s 1s 2s
All tags
Sort by
Search icon

Interview problems

optimal java solution

public class Solution
{
    public static Node sortList(Node head) {
        // Write your code here
        if (head==null||head.next==null) return head;

        Node zerohead=new Node(-1);
        Node firsthead=new Node(-1);
        Node secondhead=new Node(-1);

        Node zero=zerohead;
        Node first=firsthead;
        Node second=secondhead;
        Node temp=head;
        while (temp!=null) {
            if (temp.data==0) {
                zero.next=temp;
                zero=zero.next;
            }
            else if (temp.data==1) {
                first.next=temp;
                first=first.next;
            }
            else{
                second.next=temp;
                second=second.next;
            }
            temp=temp.next;
        }
        zero.next=firsthead.next;
        first.next=secondhead.next;
        second.next=null;

        Node newHead=zerohead.next;
        return newHead;
    }
}
28 views
0 replies
1 upvote

Interview problems

C++ solution O(n) TM without data replacement

void populate(Node* &tail,Node* curr){

    tail->next=curr;

    tail = curr;

}

Node* sortList(Node *head){

   

    Node* zerohead = new Node(-1);

    Node* zerotail = zerohead;

    Node* onehead = new Node(-1);

    Node* onetail = onehead;

    Node* twohead = new Node(-1);

    Node* twotail = twohead;

 

    Node* curr = head;

    while(curr!=NULL){

        int value  = curr->data;

        if(value==0){

            populate(zerotail,curr);

 

        }

        else if(value==1){

            populate(onetail,curr);

        }

        else if(value==2){

            populate(twotail,curr);

        }

        curr = curr->next;

    }

    // merge 3 list

    if(onehead->next!=NULL){

        zerotail->next = onehead->next;

 

    }

    else{

        zerotail->next = twohead->next;

    }

    onetail->next = twohead->next;

    twotail->next = NULL;

    head = zerohead ->next;

    delete(zerohead);

    delete(onehead);

    delete(twohead);

    return head;

 

}

21 views
0 replies
0 upvotes

Interview problems

C++ easy slution if data replacement is allowed

/*

Following is the class structure of the Node class:

 

class Node

{

public:

    int data;

    Node *next;

    Node()

    {

        this->data = 0;

        next = NULL;

    }

    Node(int data)

    {

        this->data = data; 

        this->next = NULL;

    }

    Node(int data, Node* next)

    {

        this->data = data;

        this->next = next;

    }

};

*/

 

Node* sortList(Node *head){

    // Write your code here.

    int zero = 0;

    int one =0;

    int two = 0;

    Node* temp = head;

    while(temp!=NULL){

        if(temp->data == 0){

            zero++;

        }

        else if(temp->data ==1){

            one++;

        }

        else{

            two++;

        }

        temp = temp->next;

    }

    temp = head;

    while(temp!=NULL){

        if(zero!=0){

            temp->data = 0;

            zero--;

        }

        else if (one!=0){

            temp->data = 1;

            one--;

        }

        else if(two!=0){

            temp->data = 2;

            two--;

        }

        temp = temp->next;

    }

    return head;

 

}

programming

5 views
0 replies
0 upvotes

Interview problems

C++ solution using dummy nodes and without data replacement

void insertAtTail(Node *&tail, Node *temp) {
  tail->next = temp;
  tail = temp;
}
Node *sortList(Node *head) {
  // Write your code here.
  Node *temp = head;
  Node *zeroHead = new Node(-1);
  Node *zeroTail = zeroHead;
  Node *oneHead = new Node(-1);
  Node *oneTail = oneHead;
  Node *twoHead = new Node(-1);
  Node *twoTail = twoHead;

  while (temp != NULL) {
    int val = temp->data;
    if (val == 0) {
      insertAtTail(zeroTail, temp);
    } else if (val == 1) {
      insertAtTail(oneTail, temp);
    } else if (val == 2) {
      insertAtTail(twoTail, temp);
    }
    temp = temp->next;
  }

  if (oneHead->next != NULL) {
    zeroTail->next = oneHead->next;
  } else {
    zeroTail->next = twoHead->next;
  }
  oneTail->next = twoHead->next;
  twoTail->next = NULL;

  head = zeroHead->next;

  delete zeroHead;
  delete oneHead;
  delete twoHead;

  return head;
}
17 views
0 replies
0 upvotes

Interview problems

C++ Solution without doing data replacement by doing Links/pointers replacement

void insertAtTail(Node* &tail, Node* curr) {

    tail->next = curr;
    tail = curr;
}
Node* sortList(Node *head) {

    Node* zeroHead = new Node(-1);
    Node* zeroTail = zeroHead;
    Node* oneHead = new Node(-1);
    Node* oneTail = oneHead;
    Node* twoHead = new Node(-1);
    Node* twoTail = twoHead;

    Node* curr = head;
    // creating sub nodes
    while(curr!=NULL) {

        int value = curr->data;

        if(value == 0) {
            insertAtTail(zeroTail,curr);
        }
        else if (value == 1){
            insertAtTail(oneTail,curr);
        }
        else if (value == 2){
            insertAtTail(twoTail,curr);
        }
        curr=curr->next;
    }
    // merging
    if(oneHead->next != NULL) {
        zeroTail->next = oneHead->next;
    }
    else {
        zeroTail->next = twoHead->next;
    }
    oneTail->next = twoHead->next;
    twoTail->next = NULL;

    // head setup
    head = zeroHead->next;

    // deletion
    delete zeroHead;
    delete oneHead;
    delete twoHead;
    // returning head
    
    return head;
}

programming

algorithms

datastructures

beginners

5 views
0 replies
1 upvote

Interview problems

Easiest C++ Solution and better than 100% of C++ solutions

Node* sortList(Node *head){
    // Write your code here.
    int zeroCount = 0;
    int firstCount = 0;
    int secondCount = 0;

    Node* temp = head;

    while(temp != NULL) {
        if(temp->data == 0)
            zeroCount++;
        else if (temp->data == 1)
            firstCount++;
        else if (temp->data == 2)
            secondCount++;

        temp = temp->next;
    }
    temp = head;
    while(temp != NULL) {
        if(zeroCount != 0){
            temp->data = 0;
            zeroCount--;
        }
        else if(firstCount != 0) {
            temp->data = 1;
            firstCount--;
        }
        else if(secondCount != 0){
            temp->data = 2;
            secondCount--;
        }
        temp = temp->next;
    }
    return head;
}
9 views
0 replies
0 upvotes

Interview problems

easy python O(n)

class Node:

    def __init__(self, data):

        self.data = data

        self.next = None

        

 

def sortList(head):

    # Write your code here

    zerohead=Node(-1)

    onehead=Node(-1)

    twohead=Node(-1)

 

    zero=zerohead

    one=onehead

    two=twohead

    temp=head

    while temp!=None:

        if temp.data==0:

            zero.next=temp

            zero=zero.next

        elif temp.data==1:

            one.next=temp

            one=one.next

        else:

            two.next=temp

            two=two.next

        temp=temp.next

    if one.data:

        zero.next=onehead.next

    else:

        zero.next=twohead.next

    one.next=twohead.next

    two.next=None

    return zerohead.next

12 views
0 replies
0 upvotes

Interview problems

easy to understand | well define code

Node *sortList(Node *head) {

  // Write your code here.

  int a = 0, b = 0, c = 0;

  Node*temp = head;

  while(temp!=NULL)

  {

      if(temp->data==0)

      {

          a++;

      }

      else if(temp->data==1)

      {

          b++;

      }

      else if(temp->data==2)

      {

          c++;

      }

      temp=temp->next;

      

  }

  temp=head;

  while(temp!=NULL)

  {

      if(a!=0)

      {

          temp->data=0;

          a--;

      }

      else if(b!=0)

      {

          temp->data=1;

          b--;

      }

      else if(c!=0)

      {

          temp->data=2;

          c--;

      }

      temp=temp->next;

  }

  return head;

}

32 views
0 replies
1 upvote

Interview problems

sort 0,1,2

Node* sortList(Node *head){

// Write your code here.

int zerocount=0;

int onecount=0;

int twocount=0;

Node* temp=head;

while(temp!=NULL){

if(temp->data==0){

zerocount++;

}

else if(temp->data==1){

onecount++;

}

else if(temp->data==2){

twocount++;

}

}

temp=head;

while(temp!=NULL){

if(zerocount!=0){

temp->data=0;

zerocount--;

}

else if(onecount!=0){

temp->data=1;

onecount--;

}

else if(twocount!=0){

temp->data=2;

twocount--;

}

temp=temp->next;

}

return head;

}

14 views
0 replies
0 upvotes

Interview problems

Easy and brute force approach

 

Node* sortList(Node *head){

    int zero = 0;

    int one = 0;

    int two = 0;

 

    Node* temp = head; 

    while( temp != NULL){

        if( temp -> data == 0) zero++; 

        else if( temp -> data == 1) one++; 

        else two++; 

        temp = temp -> next; 

    }

    temp = head; 

 

    while( temp != NULL){

        if( zero != 0){

            temp -> data = 0;

            zero--;

        }else if( one != 0){

            temp -> data = 1; 

            one--;

        }else if( two != 0){

            temp -> data = 2; 

            two--;

        }

        temp = temp -> next;

    }

 

    return head;

}

19 views
0 replies
0 upvotes
Full screen
Console