Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Sorts a list containing 0, 1, and 2 (without moving the node)
- Node* sortList012(Node *head) {
- // Start and end of list of zeros
- Node *_0st = NULL, *_0end = NULL;
- // Start and end of list of ones
- Node *_1st = NULL, *_1end = NULL;
- // Start and end of list of twos
- Node *_2st = NULL, *_2end = NULL;
- Node *ptr = head;
- while(ptr)
- {
- Node *next = ptr->next;
- switch(ptr->data)
- {
- case 0:
- if(!_0st) // first zero to come
- {
- _0st = ptr;
- }
- else
- {
- _0end->next = ptr;
- }
- _0end = ptr;
- if(_1st) _0end->next = _1st; // link it the start of 1 ie 0 .... 0 -> 1 ....
- if(!_1st && _2st) _0end->next = _2st; // if there is no 1 but 2 ie 0 .... 0 -> 2 ....
- break;
- case 1:
- if(!_1st) // first one to come
- {
- _1st = ptr;
- if(_0end) _0end->next = _1st; // link it to the end of 0s
- }
- else
- {
- _1end->next = ptr;
- }
- _1end = ptr;
- _1end->next = _2st;
- break;
- case 2:
- if(!_2st)
- {
- _2st = ptr;
- if(_1end) _1end->next = _2st; // link it to the end of 1s ie 0 .... 0 -> 1 ....
- else if(_0end) _0end->next = _2st; // if there is no 1 but 0 ie 0 .... 0 -> 2 ....
- }
- else
- {
- _2end->next = ptr;
- }
- _2end = ptr;
- _2end->next = NULL;
- break;
- }
- ptr = next;
- }
- // start of zeros is the start of the linked list
- return _0st;
- }
Advertisement
Add Comment
Please, Sign In to add comment