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 0s ( say ‘m’ ) & 1s ( 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
else {
while (ptr->next != NULL)
ptr = ptr->next;
ptr->next = getNewNode(data);
}
}

// create a list
node *createList() {
}

// traverse the list
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
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;
}
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)
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() {