**Problem :- **

Sort a linked list where each node element is either **1** or **0**.

**Solution :- **

**Approach 1** :: Iterate through the list of size **m + n** twice.

**1st iteration** to count the no. of **0**s ( say **'m'** ) & **1**s ( say **'n'** ).

**2nd iteration** to put **0** in first **'m'** nodes & **1** in last **'n'** nodes.

**Approach 2** :: Maintain two pointers, **start** to iterate over the list & **ptr** which points to the first element in the list with data as **1**.

While iterating over the list, whenever a node with data **0** is seen, swap the data of the node with **ptr** and make
**ptr** point to next node. This approach is better that 1st approach since it requires one iteration only.

See the implementation of both the approaches below.

**#include<iostream>**
**using namespace** std;
*// list node structure*
**typedef struct** list_node {
**int** data;
**struct** list_node *next;
}node;
*// create new node*
node *getNewNode(**int** data) {
node *new_node = **new** node;
new_node->data = data;
new_node->next = NULL;
**return** new_node;
}
*// append a node to the list*
**void** addNodeToList(node **head, **int** data) {
**if** (*head == NULL)
*head = getNewNode(data);
**else** {
node *ptr = *head;
**while** (ptr->next != NULL)
ptr = ptr->next;
ptr->next = getNewNode(data);
}
}
*// create a list*
node *createList() {
node *head = NULL;
addNodeToList(&head,1);
addNodeToList(&head,0);
addNodeToList(&head,0);
addNodeToList(&head,1);
addNodeToList(&head,0);
**return** head;
}
*// traverse the list*
**void** traverseList(node *head) {
node *ptr = head;
**while** (ptr != NULL) {
cout<<ptr->data<<" ";
ptr = ptr->next;
}
}
*//sort the list (approach1)
//traverse the list twice
//first iteration :- count the no. of 0s & 1s
//2nd iteration :- replace node values with count_0s and count_1s*
**void** sortList1(node **head) {
node *start = *head;
**int** count_0s = 0, count_1s = 0;
*// count the no. of 0s and 1s*
**while** (start != NULL) {
(start->data == 0) ? count_0s++ : count_1s++;
start = start->next;
}
start = *head;
**while** (start != NULL) {
*// fill the first count_0 nodes with 0*
**if** (count_0s > 0) {
start->data = 0;
start = start->next;
count_0s--;
**continue**;
}
*// fill the last count_1 nodes with 1*
**if** (count_1s > 0) {
start->data = 1;
start = start->next;
count_1s--;
}
}
}
*// sort the list (approach2)
// traverse the list only once (efficient)*
**void** sortList2(node **head) {
node *start = *head;
node *ptr = NULL; *// points to first '1' in the list*
**while** (start != NULL) {
**if** (start->data == 1 && ptr == NULL) {
ptr = start; *// first '1' in the list is found*
}
**else if** (start->data == 0 && ptr != NULL) {
*//swap the data of start and ptr nodes*
**int** temp = ptr->data;
ptr->data = start->data;
start->data = temp;
*//ptr points to next node*
ptr = ptr->next;
}
start = start->next;
}
}
*// main*
**int** main() {
node *head = createList();
cout<<"\nOriginal List :-\n";
traverseList(head);
sortList1(&head);
*//sortList2(&head);*
cout<<"\nSorted List :-\n";
traverseList(head);
cout<<endl;
**return** 0;
}