The best programs are written so that computing machines can perform them quickly and so that human beings can understand them clearly. A programmer is ideally an essayist who works with traditional aesthetic and literary forms as
well as mathematical concepts, to communicate the way that an algorithm works and to convince a reader that the results will be correct. Donald E. Knuth

Linked List

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
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;
}

Back | Next

All problems on Linked List
* Insert, Delete and Search nodes in a single linked list
* Insert, Delete and Search nodes in a double linked list
* Sort a linked list where each node element is either 1 or 0
* Reverse a linked list in an efficient manner
* Merge two sorted linked lists
* Detect a loop in a given linked list