Problem

Submissions

Hints & solutions

Discuss

Sort linked list of 0s 1s 2s

Easy

0/40

Average time to solve is 10m

Contributed by

256 upvotes

Asked in companies

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 1

Hint 2

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

Approaches (2)

Approach 1

Approach 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).

(100% EXP penalty)

Sort linked list of 0s 1s 2s

Console