Sort a linked list of 0s, 1s and 2s Easy 0 attempts
GeeksforGeeks ↗

Sort a linked list of 0s, 1s and 2s

Easy Linked List GeeksforGeeks

You're given a linked list where every node's value is 0, 1, or 2. Sort the list so all 0s come first, followed by all 1s, then all 2s — done by overwriting node values rather than rearranging the nodes themselves.

Input Format
Implement sortList012(head). Inputs below show JavaScript function arguments; there is no stdin parsing. Linked lists use value arrays. The editor passes nodes with val and next properties; [] becomes null.
Output Format
Modify argument 1 in place. The editor compares its final value; the function return value is ignored. Returned list heads are displayed as value arrays; a null head is [].

Sample Input and Output

Example 1 · Run Sample

Input
head = [1,2,0,1,2,0]
Output
[0,0,1,1,2,2]

Example 2

Input
head = [0]
Output
[0]
Constraints
  • 1 <= N <= 10^3
  • 0 <= Node.val <= 2
Test Cases (2)
Case 1
Args: [[1,2,0,1,2,0]] Expected: [0,0,1,1,2,2]
Case 2
Args: [[0]] Expected: [0]
Topics
Linked List

Count and Overwrite

javascript
function sortList012(head) {
  let c = [0,0,0], curr = head;
  while (curr) { c[curr.val]++; curr = curr.next; }
  curr = head;
  for (let v = 0; v <= 2; v++) while (c[v]-- > 0) { curr.val = v; curr = curr.next; }
}

Time: O(n) | Space: O(1)

Saved in this browser only. Private to you.

JavaScript