Sort a LL of 0's 1's and 2's
Linked-List
Logic Building
Medium
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.
Examples:
Input: head -> 1 -> 0 -> 2 -> 0 -> 1
Output: head -> 0 -> 0 -> 1 -> 1 -> 2
Explanation: The values after sorting are [0, 0, 1, 1, 2].
Input: head -> 1 -> 1 -> 1 -> 0
Output: head -> 0 -> 1 -> 1 -> 1
Explanation: The values after sorting are [0, 1, 1, 1].
Input: head -> 2 -> 2 -> 1 -> 2
Constraints
- 0 <= number of nodes in the Linked List <= 105
- 0 <= ListNode.val <= 2
Hints
- Use three dummy pointers (zero_head, one_head, two_head) to track separate linked lists for 0s, 1s, and 2s.
- Traverse the original list and distribute nodes into the corresponding lists. Merge the three lists by updating links: Connect the 0s list → 1s list → 2s list Ensure the tail of the last list points to NULL.
Company Tags
Target
Bungie
Zoho
Snowflake
Alibaba
Oracle
Uber
Rockstar Games
Activision Blizzard
Swiggy
Splunk
Bain & Company
eBay
Siemens Healthineers
Salesforce
Seagate Technology
Reddit
Chewy
Pinterest
American Express
Visa
Ubisoft
Texas Instruments
Wayfair
Roblox
Google
Microsoft
Amazon
Meta
Apple
Netflix
Adobe
Editorial
Intuition
Since there are only 3 distinct values in the linked list, it's straightforward to count the occurrences of 0s, 1s, and 2s. After counting, we can overwrite the linked list nodes based on these frequencies.Approach
- Take 3 variables to maintain the count of 0, 1, and 2.
- Traverse the linked list to count the occurrences of each value.
- In the second traversal of the linked list, overwrite the first 'a' nodes with '0', the next 'b' nodes with '1', and the remaining 'c' nodes with '2' based on the counts.
Dry Run
Solution
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104
#include <bits/stdc++.h>
using namespace std;
// Definition of singly linked list:
struct ListNode {
int val;
ListNode* next;
ListNode() {
val = 0;
next = NULL;
}
ListNode(int data1) {
val = data1;
next = NULL;
}
ListNode(int data1, ListNode* next1) {
val = data1;
next = next1;
}
};
class Solution {
public:
// Function to sort the linked list
ListNode* sortList(ListNode* head) {
// Initialize counts
int c0 = 0, c1 = 0, c2 = 0;
ListNode* temp = head;
/* Count the number of 0s,
1s, and 2s in the list*/
while (temp != NULL) {
if (temp->val == 0)
c0++;
else if (temp->val == 1)
c1++;
else if (temp->val == 2)
c2++;
temp = temp->next;
}
temp = head;
/* Reassign values to
the nodes based on
the counts*/
while (temp != NULL) {
if (c0 > 0) {
temp->val = 0;
c0--;
} else if (c1 > 0) {
temp->val = 1;
c1--;
} else if (c2 > 0) {
temp->val = 2;
c2--;
}
temp = temp->next;
}
return head;
}
};
// Function to print linked list
void printList(ListNode* head) {
while (head != NULL) {
cout << head->val << " ";
head = head->next;
}
cout << endl;
}
// Function to create new node
ListNode* newNode(int data) {
ListNode* node = new ListNode(data);
return node;
}
int main() {
// Creating a linked list
ListNode* head = newNode(1);
head->next = newNode(2);
head->next->next = newNode(0);
head->next->next->next = newNode(1);
head->next->next->next->next = newNode(2);
head->next->next->next->next->next = newNode(0);
head->next->next->next->next->next->next = newNode(1);
// Print original list
cout << "Original list: ";
printList(head);
// Sort the list
Solution sol;
head = sol.sortList(head);
// Print sorted list
cout << "Sorted list: ";
printList(head);
return 0;
}123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102
import java.util.*;
// Definition of singly linked list:
class ListNode {
int val;
ListNode next;
ListNode() {
val = 0;
next = null;
}
ListNode(int data1) {
val = data1;
next = null;
}
ListNode(int data1, ListNode next1) {
val = data1;
next = next1;
}
}
class Solution {
// Function to sort the linked list
public ListNode sortList(ListNode head) {
// Initialize counts
int c0 = 0, c1 = 0, c2 = 0;
ListNode temp = head;
/* Count the number of 0s,
1s, and 2s in the list */
while (temp != null) {
if (temp.val == 0)
c0++;
else if (temp.val == 1)
c1++;
else if (temp.val == 2)
c2++;
temp = temp.next;
}
temp = head;
/* Reassign values to
the nodes based on
the counts */
while (temp != null) {
if (c0 > 0) {
temp.val = 0;
c0--;
} else if (c1 > 0) {
temp.val = 1;
c1--;
} else if (c2 > 0) {
temp.val = 2;
c2--;
}
temp = temp.next;
}
return head;
}
}
// Function to print linked list
public class Main {
public static void printList(ListNode head) {
while (head != null) {
System.out.print(head.val + " ");
head = head.next;
}
System.out.println();
}
// Function to create new node
public static ListNode newNode(int data) {
ListNode node = new ListNode(data);
return node;
}
public static void main(String[] args) {
// Creating a linked list
ListNode head = newNode(1);
head.next = newNode(2);
head.next.next = newNode(0);
head.next.next.next = newNode(1);
head.next.next.next.next = newNode(2);
head.next.next.next.next.next = newNode(0);
head.next.next.next.next.next.next = newNode(1);
// Print original list
System.out.print("Original list: ");
printList(head);
// Sort the list
Solution sol = new Solution();
head = sol.sortList(head);
// Print sorted list
System.out.print("Sorted list: ");
printList(head);
}
}
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677
# Definition of singly linked list:
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
# Function to sort the linked list
def sortList(self, head):
# Initialize counts
c0 = 0
c1 = 0
c2 = 0
temp = head
# Count the number of 0s,
# 1s, and 2s
while temp is not None:
if temp.val == 0:
c0 += 1
elif temp.val == 1:
c1 += 1
elif temp.val == 2:
c2 += 1
temp = temp.next
temp = head
# Reassign values to the
# nodes based on the counts
while temp is not None:
if c0 > 0:
temp.val = 0
c0 -= 1
elif c1 > 0:
temp.val = 1
c1 -= 1
elif c2 > 0:
temp.val = 2
c2 -= 1
temp = temp.next
return head
# Function to print linked list
def printList(head):
while head is not None:
print(head.val, end=" ")
head = head.next
print()
# Function to create new node
def newNode(data):
return ListNode(data)
if __name__ == "__main__":
# Creating a linked list
head = newNode(1)
head.next = newNode(2)
head.next.next = newNode(0)
head.next.next.next = newNode(1)
head.next.next.next.next = newNode(2)
head.next.next.next.next.next = newNode(0)
head.next.next.next.next.next.next = newNode(1)
# Print original list
print("Original list: ", end="")
printList(head)
# Sort the list
sol = Solution()
head = sol.sortList(head)
# Print sorted list
print("Sorted list: ", end="")
printList(head)
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687
// Definition of singly linked list:
class ListNode {
constructor(val = 0, next = null) {
this.val = val;
this.next = next;
}
}
class Solution {
// Function to sort the linked list
sortList(head) {
// Initialize counts
let c0 = 0, c1 = 0, c2 = 0;
let temp = head;
/* Count the number of 0s,
1s, and 2s in the list */
while (temp !== null) {
if (temp.val === 0)
c0++;
else if (temp.val === 1)
c1++;
else if (temp.val === 2)
c2++;
temp = temp.next;
}
temp = head;
/* Reassign values to
the nodes based on
the counts */
while (temp !== null) {
if (c0 > 0) {
temp.val = 0;
c0--;
} else if (c1 > 0) {
temp.val = 1;
c1--;
} else if (c2 > 0) {
temp.val = 2;
c2--;
}
temp = temp.next;
}
return head;
}
}
// Function to print linked list
function printList(head) {
while (head !== null) {
process.stdout.write(head.val + " ");
head = head.next;
}
console.log();
}
// Function to create new node
function newNode(data) {
return new ListNode(data);
}
(function() {
// Creating a linked list
let head = newNode(1);
head.next = newNode(2);
head.next.next = newNode(0);
head.next.next.next = newNode(1);
head.next.next.next.next = newNode(2);
head.next.next.next.next.next = newNode(0);
head.next.next.next.next.next.next = newNode(1);
// Print original list
process.stdout.write("Original list: ");
printList(head);
// Sort the list
let sol = new Solution();
head = sol.sortList(head);
// Print sorted list
process.stdout.write("Sorted list: ");
printList(head);
})();
Complexity Analysis
Time Complexity: O(2N) because the code traverses the linked list twice: once while counting the frequency of 0's, 1's, and 2's, and once again while reassigning the values to the nodes. Here, N represents the length of the linked list or the number of nodes present in the linked list. Space Complexity: O(1) because no extra space is used.Intuition
Traverse the linked list to segregate nodes into three separate lists based on their values (0s, 1s, and 2s), then link these lists together to form a single sorted linked list.Approach
- Create three dummy nodes to serve as the heads of three separate lists for 0s, 1s, and 2s. Also, create pointers to track the current end of each of these lists.
- Traverse the original linked list. For each node, append it to the appropriate list (0s, 1s, or 2s) based on its value and update the corresponding pointer.
- Connect the three lists together. Link the end of the 0s list to the start of the 1s list (or directly to the 2s list if the 1s list is empty). Then, link the end of the 1s list to the start of the 2s list.
- The new head of the sorted linked list will be the node following the dummy node for 0s.
- Return the new head of the sorted linked list. This completes the process and results in a sorted linked list.
Dry Run
Solution
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117
#include <bits/stdc++.h>
using namespace std;
// Definition of singly linked list:
struct ListNode {
int val;
ListNode* next;
ListNode() {
val = 0;
next = NULL;
}
ListNode(int data1) {
val = data1;
next = NULL;
}
ListNode(int data1, ListNode* next1) {
val = data1;
next = next1;
}
};
class Solution {
public:
// Function to sort the linked list
ListNode* sortList(ListNode* head) {
/* If the list is empty or has only one
node, return as it is already sorted*/
if (head == NULL || head->next == NULL)
return head;
// Dummy nodes to point to heads of
// three lists
ListNode* zeroHead = new ListNode(-1);
ListNode* oneHead = new ListNode(-1);
ListNode* twoHead = new ListNode(-1);
// Pointers to current last nodes of
// three lists
ListNode* zero = zeroHead;
ListNode* one = oneHead;
ListNode* two = twoHead;
ListNode* temp = head;
/* Traverse the original list
and distribute the nodes
into three lists*/
while (temp != NULL) {
if (temp->val == 0) {
zero->next = temp;
zero = temp;
} else if (temp->val == 1) {
one->next = temp;
one = temp;
} else if (temp->val == 2) {
two->next = temp;
two = temp;
}
temp = temp->next;
}
// Connect the three lists together
zero->next = (oneHead->next) ? oneHead->next : twoHead->next;
one->next = twoHead->next;
two->next = NULL;
// New head of the sorted list
ListNode* newHead = zeroHead->next;
// Delete dummy nodes
delete zeroHead;
delete oneHead;
delete twoHead;
return newHead;
}
};
// Helper function to print linked list
void printList(ListNode* head) {
while (head != NULL) {
cout << head->val << " ";
head = head->next;
}
cout << endl;
}
// Helper function to create a new node
ListNode* newNode(int data) {
ListNode* node = new ListNode(data);
return node;
}
int main() {
// Creating a linked list
ListNode* head = newNode(1);
head->next = newNode(2);
head->next->next = newNode(0);
head->next->next->next = newNode(1);
head->next->next->next->next = newNode(2);
head->next->next->next->next->next = newNode(0);
head->next->next->next->next->next->next = newNode(1);
// Print original list
cout << "Original list: ";
printList(head);
// Sort the list
Solution sol;
head = sol.sortList(head);
// Print sorted list
cout << "Sorted list: ";
printList(head);
return 0;
}123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110
import java.util.*;
// Definition of singly linked list:
class ListNode {
int val;
ListNode next;
ListNode() {
val = 0;
next = null;
}
ListNode(int data1) {
val = data1;
next = null;
}
ListNode(int data1, ListNode next1) {
val = data1;
next = next1;
}
}
class Solution {
// Function to sort the linked list
public ListNode sortList(ListNode head) {
/* If the list is empty or has only one
node, return as it is already sorted */
if (head == null || head.next == null)
return head;
// Dummy nodes to point to heads of
// three lists
ListNode zeroHead = new ListNode(-1);
ListNode oneHead = new ListNode(-1);
ListNode twoHead = new ListNode(-1);
// Pointers to current last nodes of
// three lists
ListNode zero = zeroHead;
ListNode one = oneHead;
ListNode two = twoHead;
ListNode temp = head;
/* Traverse the original list
and distribute the nodes
into three lists */
while (temp != null) {
if (temp.val == 0) {
zero.next = temp;
zero = temp;
} else if (temp.val == 1) {
one.next = temp;
one = temp;
} else if (temp.val == 2) {
two.next = temp;
two = temp;
}
temp = temp.next;
}
// Connect the three lists together
zero.next = (oneHead.next != null) ? oneHead.next : twoHead.next;
one.next = twoHead.next;
two.next = null;
// New head of the sorted list
ListNode newHead = zeroHead.next;
// Delete dummy nodes
return newHead;
}
}
// Helper function to print linked list
public class Main {
public static void printList(ListNode head) {
while (head != null) {
System.out.print(head.val + " ");
head = head.next;
}
System.out.println();
}
// Helper function to create a new node
public static ListNode newNode(int data) {
return new ListNode(data);
}
public static void main(String[] args) {
// Creating a linked list
ListNode head = newNode(1);
head.next = newNode(2);
head.next.next = newNode(0);
head.next.next.next = newNode(1);
head.next.next.next.next = newNode(2);
head.next.next.next.next.next = newNode(0);
head.next.next.next.next.next.next = newNode(1);
// Print original list
System.out.print("Original list: ");
printList(head);
// Sort the list
Solution sol = new Solution();
head = sol.sortList(head);
// Print sorted list
System.out.print("Sorted list: ");
printList(head);
}
}
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586
# Definition of singly linked list:
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
# Function to sort the linked list
def sortList(self, head):
'''If the list is empty or has only one
node, return as it is already sorted'''
if head is None or head.next is None:
return head
# Dummy nodes to point to heads of
# three lists
zeroHead = ListNode(-1)
oneHead = ListNode(-1)
twoHead = ListNode(-1)
# Pointers to current last nodes of
# three lists
zero = zeroHead
one = oneHead
two = twoHead
temp = head
'''Traverse the original list
and distribute the nodes
into three lists'''
while temp is not None:
if temp.val == 0:
zero.next = temp
zero = temp
elif temp.val == 1:
one.next = temp
one = temp
elif temp.val == 2:
two.next = temp
two = temp
temp = temp.next
# Connect the three lists together
zero.next = oneHead.next if oneHead.next else twoHead.next
one.next = twoHead.next
two.next = None
# New head of the sorted list
newHead = zeroHead.next
# Return the new head
return newHead
# Helper function to print linked list
def printList(head):
while head is not None:
print(head.val, end=" ")
head = head.next
print()
# Helper function to create a new node
def newNode(data):
return ListNode(data)
if __name__ == "__main__":
# Creating a linked list
head = newNode(1)
head.next = newNode(2)
head.next.next = newNode(0)
head.next.next.next = newNode(1)
head.next.next.next.next = newNode(2)
head.next.next.next.next.next = newNode(0)
head.next.next.next.next.next.next = newNode(1)
# Print original list
print("Original list: ", end="")
printList(head)
# Sort the list
sol = Solution()
head = sol.sortList(head)
# Print sorted list
print("Sorted list: ", end="")
printList(head)
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596
// Definition of singly linked list:
class ListNode {
constructor(val = 0, next = null) {
this.val = val;
this.next = next;
}
}
class Solution {
// Function to sort the linked list
sortList(head) {
/* If the list is empty or has only one
node, return as it is already sorted */
if (head === null || head.next === null)
return head;
// Dummy nodes to point to heads of
// three lists
let zeroHead = new ListNode(-1);
let oneHead = new ListNode(-1);
let twoHead = new ListNode(-1);
// Pointers to current last nodes of
// three lists
let zero = zeroHead;
let one = oneHead;
let two = twoHead;
let temp = head;
/* Traverse the original list
and distribute the nodes
into three lists */
while (temp !== null) {
if (temp.val === 0) {
zero.next = temp;
zero = temp;
} else if (temp.val === 1) {
one.next = temp;
one = temp;
} else if (temp.val === 2) {
two.next = temp;
two = temp;
}
temp = temp.next;
}
// Connect the three lists together
zero.next = oneHead.next ? oneHead.next : twoHead.next;
one.next = twoHead.next;
two.next = null;
// New head of the sorted list
let newHead = zeroHead.next;
// Return the new head
return newHead;
}
}
// Helper function to print linked list
function printList(head) {
while (head !== null) {
process.stdout.write(head.val + " ");
head = head.next;
}
console.log();
}
// Helper function to create a new node
function newNode(data) {
return new ListNode(data);
}
(function() {
// Creating a linked list
let head = newNode(1);
head.next = newNode(2);
head.next.next = newNode(0);
head.next.next.next = newNode(1);
head.next.next.next.next = newNode(2);
head.next.next.next.next.next = newNode(0);
head.next.next.next.next.next.next = newNode(1);
// Print original list
process.stdout.write("Original list: ");
printList(head);
// Sort the list
let sol = new Solution();
head = sol.sortList(head);
// Print sorted list
process.stdout.write("Sorted list: ");
printList(head);
})();
Complexity Analysis
Time Complexity: O(N) because the code traverses the linked list once. Here, N represents the length of the linked list or the number of nodes present in the linked list. Space Complexity: O(1) because no extra space is used and we just change the links of the nodes.Frequently Occurring Doubts
Q: Why do we need three separate dummy lists instead of modifying the original list?
A: Modifying links directly while traversing can lead to broken links or require multiple scans. Using three separate lists ensures stable sorting without losing track of nodes.
Q: What happens if the input list already has sorted 0s, 1s, and 2s?
A: The algorithm processes the list normally, but no rearrangement is needed since pointers remain unchanged.
Interview Followup Questions
Q: How can this be extended to handle a linked list with arbitrary numbers instead of just 0, 1, and 2?
A: Use bucket sort logic but with hash maps to store frequency counts. Instead of three pointers, use multiple dummy lists for each unique value.
Q: Can this be modified to sort linked lists containing values from 0 to k?
A: Yes, generalize it by: Creating k+1 linked lists. Distributing nodes into respective buckets. Merging all buckets into a single list.
Notes
Code
✅ Testcase
Input: {'nums': '[1, 0, 2, 0, 1]'}
Expected:
0 0 1 1 2
0 0 1 1 2
Actual: -
Time: -
sec
Status: Waiting
Input: {'nums': '[1, 1, 1, 0]'}
Expected:
0 1 1 1
0 1 1 1
Actual: -
Time: -
sec
Status: Waiting
Input: {'nums': '[2, 2, 1, 2]'}
Expected:
1 2 2 2
1 2 2 2
Actual: -
Time: -
sec
Status: Waiting