Problem link - Sort Linked List
Problem Statement:
Given a singly linked list containing only 0s, 1s, and 2s, sort the linked list such that all 0s come before 1s which come before 2s. The function should sort the list by changing links and not by swapping data.
Approach:
The key idea to solve this problem is to count the occurrences of 0s, 1s, and 2s in the linked list, and then rearrange the linked list in the correct order based on these counts. Here’s a step-by-step explanation of how we can approach the problem:
-
Count Occurrences:
- We will traverse the entire linked list once to count how many nodes have values 0, 1, and 2. Let’s say there are count0, count1, and count2 nodes with values 0, 1, and 2 respectively.
-
Rearrange the List:
- After counting, we will again traverse the list and change the value of the nodes in the order of 0s, then 1s, and finally 2s. This rearranges the linked list such that all the 0s come first, followed by 1s, and then the 2s.
-
Update Pointers:
- This solution changes the values in the existing nodes, so it doesn’t require creating new nodes or using additional linked lists.
Time Complexity:
- O(n), where n is the number of nodes. We traverse the list twice: once for counting and once for rearranging.
Space Complexity:
- O(1), as we only use constant space for counting 0s, 1s, and 2s without extra data structures.