fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4. // Node class definition
  5. class Node {
  6. public:
  7.     int data;
  8.     Node* next;
  9.     Node(int x) : data(x), next(nullptr) {}
  10. };
  11.  
  12. class Solution {
  13. public:
  14.     Node* segregate(Node* head) {
  15.         if (!head || !head->next) return head;
  16.  
  17.         // Count occurrences of 0s, 1s, and 2s
  18.         int cnt0 = 0, cnt1 = 0, cnt2 = 0;
  19.         Node* tmp = head;
  20.         while (tmp) {
  21.             if (tmp->data == 0) cnt0++;
  22.             else if (tmp->data == 1) cnt1++;
  23.             else if (tmp->data == 2) cnt2++;
  24.             tmp = tmp->next;
  25.         }
  26.  
  27.         // Overwrite the list with sorted values
  28.         tmp = head;
  29.         while (cnt0--) { tmp->data = 0; tmp = tmp->next; }
  30.         while (cnt1--) { tmp->data = 1; tmp = tmp->next; }
  31.         while (cnt2--) { tmp->data = 2; tmp = tmp->next; }
  32.  
  33.         return head;
  34.     }
  35. };
  36.  
  37. // Helper function to create a linked list from an array
  38. Node* createList(int arr[], int n) {
  39.     if (n == 0) return nullptr;
  40.     Node* head = new Node(arr[0]);
  41.     Node* current = head;
  42.     for (int i = 1; i < n; i++) {
  43.         current->next = new Node(arr[i]);
  44.         current = current->next;
  45.     }
  46.     return head;
  47. }
  48.  
  49. // Helper function to print the linked list
  50. void printList(Node* head) {
  51.     Node* current = head;
  52.     while (current) {
  53.         cout << current->data << " ";
  54.         current = current->next;
  55.     }
  56.     cout << endl;
  57. }
  58.  
  59. // Helper function to delete the linked list
  60. void deleteList(Node* head) {
  61.     while (head) {
  62.         Node* temp = head;
  63.         head = head->next;
  64.         delete temp;
  65.     }
  66. }
  67.  
  68. int main() {
  69.     Solution sol;
  70.  
  71.     // Test Case 1: Mixed 0s, 1s, and 2s
  72.     int arr1[] = {1, 2, 0, 1, 2, 0};
  73.     int n1 = sizeof(arr1)/sizeof(arr1[0]);
  74.     Node* head1 = createList(arr1, n1);
  75.     cout << "Original List 1: ";
  76.     printList(head1);
  77.     head1 = sol.segregate(head1);
  78.     cout << "Sorted List 1: ";
  79.     printList(head1);
  80.     deleteList(head1);
  81.  
  82.     // Test Case 2: All 0s
  83.     int arr2[] = {0, 0, 0};
  84.     int n2 = sizeof(arr2)/sizeof(arr2[0]);
  85.     Node* head2 = createList(arr2, n2);
  86.     cout << "Original List 2: ";
  87.     printList(head2);
  88.     head2 = sol.segregate(head2);
  89.     cout << "Sorted List 2: ";
  90.     printList(head2);
  91.     deleteList(head2);
  92.  
  93.     // Test Case 3: Already sorted
  94.     int arr3[] = {0, 0, 1, 1, 2, 2};
  95.     int n3 = sizeof(arr3)/sizeof(arr3[0]);
  96.     Node* head3 = createList(arr3, n3);
  97.     cout << "Original List 3: ";
  98.     printList(head3);
  99.     head3 = sol.segregate(head3);
  100.     cout << "Sorted List 3: ";
  101.     printList(head3);
  102.     deleteList(head3);
  103.  
  104.     // Test Case 4: Single element
  105.     int arr4[] = {1};
  106.     int n4 = sizeof(arr4)/sizeof(arr4[0]);
  107.     Node* head4 = createList(arr4, n4);
  108.     cout << "Original List 4: ";
  109.     printList(head4);
  110.     head4 = sol.segregate(head4);
  111.     cout << "Sorted List 4: ";
  112.     printList(head4);
  113.     deleteList(head4);
  114.  
  115.     // Test Case 5: Empty list
  116.     Node* head5 = nullptr;
  117.     cout << "Original List 5: ";
  118.     printList(head5);
  119.     head5 = sol.segregate(head5);
  120.     cout << "Sorted List 5: ";
  121.     printList(head5);
  122.     deleteList(head5);
  123.  
  124.     return 0;
  125. }
Success #stdin #stdout 0s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Original List 1: 1 2 0 1 2 0 
Sorted List 1: 0 0 1 1 2 2 
Original List 2: 0 0 0 
Sorted List 2: 0 0 0 
Original List 3: 0 0 1 1 2 2 
Sorted List 3: 0 0 1 1 2 2 
Original List 4: 1 
Sorted List 4: 1 
Original List 5: 
Sorted List 5:
https://ideone.com/qXtx7W
language:
C++14 (gcc 8.3)
created:
12 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!