Sorting 0's, 1's, and 2's in a Linked List by Changing Links

Problem Statement

Given a singly linked list containing 0's, 1's, and 2's, the objective is to sort the list in non-decreasing order without using extra space. The sorting should be done by changing the links 

Examples

Example 1:

Input: List = {1 -> 0 -> 2 -> 1 -> 0}
Output: {0 -> 0 -> 1 -> 1 -> 2}

Different Approaches

1️⃣ Counting Sort Using Three Pointers

Algorithm:

1. Initialize three pointers, zeroPtr, onePtr, and twoPtr to null.
2. Traverse the linked list.
3. For each node:
   1. If the node value is 0:
      1. If zeroPtr is null, assign zeroPtr to the current node.
      2. Otherwise, append the current node to the end of the list pointed by zeroPtr and update zeroPtr to the current node.
   2. If the node value is 1:
      1. If onePtr is null, assign onePtr to the current node.
      2. Otherwise, append the current node to the end of the list pointed by onePtr and update onePtr to the current node.
   3. If the node value is 2:
      1. If twoPtr is null, assign twoPtr to the current node.
      2. Otherwise, append the current node to the end of the list pointed by twoPtr and update twoPtr to the current node.
4. After traversal, join the three lists (if not null), linking zeroPtr to onePtr and onePtr to twoPtr.
5. Return the head of the sorted list.

Code:

#include <iostream>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* sortList(ListNode* head) {
    ListNode* zeroPtr = nullptr;
    ListNode* onePtr = nullptr;
    ListNode* twoPtr = nullptr;
    
    ListNode* curr = head;
    
    while (curr != nullptr) {
        if (curr->val == 0) {
            if (zeroPtr == nullptr) {
                zeroPtr = curr;
            } else {
                zeroPtr->next = curr;
                zeroPtr = curr;
            }
        } else if (curr->val == 1) {
            if (onePtr == nullptr) {
                onePtr = curr;
            } else {
                onePtr->next = curr;
                onePtr = curr;
            }
        } else { // curr->val == 2
            if (twoPtr == nullptr) {
                twoPtr = curr;
            } else {
                twoPtr->next = curr;
                twoPtr = curr;
            }
        }
        curr = curr->next;
    }
    
    if (zeroPtr != nullptr) {
        zeroPtr->next = (onePtr != nullptr) ? onePtr : twoPtr;
    }
    if (onePtr != nullptr) {
        onePtr->next = twoPtr;
    }
    if (twoPtr != nullptr) {
        twoPtr->next = nullptr;
    }
    
    return (zeroPtr != nullptr) ? head : ((onePtr != nullptr) ? zeroPtr->next : onePtr);
}

void printList(ListNode* head) {
    while (head != nullptr) {
        std::cout << head->val << " ";
        head = head->next;
    }
    std::cout << std::endl;
}

int main() {
    ListNode* head = new ListNode(1);
    head->next = new ListNode(0);
    head->next->next = new ListNode(2);
    head->next->next->next = new ListNode(1);
    head->next->next->next->next = new ListNode(0);
    
    std::cout << "Original List: ";
    printList(head);
    
    head = sortList(head);
    
    std::cout << "Sorted List: ";
    printList(head);
    
    return 0;
}

OR:

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        // Base case: If the list is empty or has only one node, it's already sorted
        if (!head || !head->next) {
            return head;
        }

        // Create dummy nodes to represent three separate linked lists:
        // - `zero` for nodes with value 0
        // - `one` for nodes with value 1
        // - `two` for nodes with value 2
        ListNode* zero = new ListNode(0);
        ListNode* zeroItr = zero; // Iterator for the `zero` list

        ListNode* one = new ListNode(0);
        ListNode* oneItr = one; // Iterator for the `one` list

        ListNode* two = new ListNode(0);
        ListNode* twoItr = two; // Iterator for the `two` list

        // Traverse the original linked list and distribute nodes to the respective lists
        ListNode* current = head;
        while (current) {
            if (current->val == 0) {
                // If the current node's value is 0, add it to the `zero` list
                zeroItr->next = current;
                zeroItr = zeroItr->next; // Move the iterator forward
            } else if (current->val == 1) {
                // If the current node's value is 1, add it to the `one` list
                oneItr->next = current;
                oneItr = oneItr->next; // Move the iterator forward
            } else {
                // If the current node's value is 2, add it to the `two` list
                twoItr->next = current;
                twoItr = twoItr->next; // Move the iterator forward
            }
            current = current->next; // Move to the next node in the original list
        }

        // Combine the three lists:
        // - Link the end of the `zero` list to the beginning of the `one` list (or `two` if `one` is empty)
        // - Link the end of the `one` list to the beginning of the `two` list
        zeroItr->next = one->next ? one->next : two->next;
        oneItr->next = two->next;

        // Mark the end of the `two` list as null to terminate the combined list
        twoItr->next = nullptr;

        // Get the head of the final sorted list, which is the next node after the dummy `zero` node
        ListNode* sortedHead = zero->next;

        // Clean up the dummy nodes to free memory
        delete zero;
        delete one;
        delete two;

        // Return the head of the sorted list
        return sortedHead;
    }
};

Complexity Analysis:

• Time Complexity: O(n), where n is the number of nodes in the current linked list.
• Space Complexity: O(1)
  • As we are using constant extra space regardless of  input size.