shashwat2

Sorting a linked list with 0s 1s and 2s

Nov 23rd, 2014
268
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.40 KB | None | 0 0
  1. // Sorts a list containing 0, 1, and 2 (without moving the node)
  2. Node* sortList012(Node *head) {
  3.     // Start and end of list of zeros
  4.     Node *_0st = NULL, *_0end = NULL;
  5.     // Start and end of list of ones
  6.     Node *_1st = NULL, *_1end = NULL;
  7.     // Start and end of list of twos
  8.     Node *_2st = NULL, *_2end = NULL;
  9.    
  10.     Node *ptr = head;
  11.     while(ptr)
  12.     {
  13.         Node *next = ptr->next;
  14.         switch(ptr->data)
  15.         {
  16.             case 0:
  17.                 if(!_0st)       // first zero to come
  18.                 {
  19.                     _0st = ptr;
  20.                 }
  21.                 else
  22.                 {
  23.                     _0end->next = ptr;
  24.                 }
  25.                 _0end = ptr;
  26.                 if(_1st) _0end->next = _1st;            // link it the start of 1  ie 0 .... 0 -> 1 ....
  27.                 if(!_1st && _2st) _0end->next = _2st;   // if there is no 1 but 2  ie 0 .... 0 -> 2 ....
  28.                 break;
  29.             case 1:
  30.                 if(!_1st)       // first one to come
  31.                 {
  32.                     _1st = ptr;
  33.                     if(_0end) _0end->next = _1st;       // link it to the end of 0s
  34.                 }
  35.                 else
  36.                 {
  37.                     _1end->next = ptr;
  38.                 }
  39.                 _1end = ptr;
  40.                 _1end->next = _2st;
  41.                 break;
  42.             case 2:
  43.                 if(!_2st)
  44.                 {
  45.                     _2st = ptr;
  46.                     if(_1end) _1end->next = _2st;           // link it to the end of 1s  ie 0 .... 0 -> 1 ....
  47.                     else if(_0end) _0end->next = _2st;      // if there is no 1 but 0   ie 0 .... 0 -> 2 ....
  48.                 }
  49.                 else
  50.                 {
  51.                     _2end->next = ptr;
  52.                 }
  53.                 _2end = ptr;
  54.                 _2end->next = NULL;
  55.                 break;
  56.         }
  57.         ptr = next;
  58.     }
  59.     // start of zeros is the start of the linked list
  60.     return _0st;
  61. }
Advertisement
Add Comment
Please, Sign In to add comment