778. Sort a Linked List of 0's 1's and 2's

Given the head of a singly linked list consisting of only 0, 1 or 2.

Sort the given linked list and return the head of the modified list.

Do it in-place by changing the links between the nodes without creating new nodes.

Example 1:

Input: linkedList = [1, 0, 2, 0 , 1]

Output: [0, 0, 1, 1, 2]

Explanation: The values after sorting are [0, 0, 1, 1, 2].

Example 2:

Input: linkedList = [1, 1, 1, 0]

Output: [0, 1, 1, 1]

Explanation: The values after sorting are [0, 1, 1, 1].

Now Your Turn!

Pick the correct output for the given input

Input: linkedList = [2, 2, 1, 2]

Still unsure what the problem is asking ?

Let’s go through a few more examples, step by step, to make it clearer.

Constraints:

  • 0 <= number of nodes in the Linked List <= 105
  • 0 <= ListNode.val <= 2

Hints

Frequently Occurring Doubts

Interview Follow-up Questions

0
/*
Definition of singly linked list:
class ListNode{
public:
int data;
ListNode *next;
ListNode() : data(0), next(nullptr) {}
ListNode(int x) : data(x), next(nullptr) {}
ListNode(int x, ListNode *next) : data(x), next(next) {}
};
*/
 
class Solution {
public:
ListNode* sortList(ListNode* &head) {
//your code goes here
}
};
Test Case

Input:

Linked List
to save your code