Sorting a linked list

 

 /**Algorithm best suited to sort a linked list. 
  * 
  * Write a C program to implement that algorithm. 
  * Modified quick sort should work. 
  * 
  * ex: 4 8 2 9 5 3 
  *   4 2 8 9 5 3 
  *   4 2 3 9 5 8 
  */ 

 #include "Common.h" 

 typedef struct _node { 
      struct _node *next; 
      int value; 
 } Node; 

 void swap(Node* node1, Node* node2) { 
      int temp = node1->value; 
      node1->value = node2->value; 
      node2->value = temp; 
 } 

 void sortLinkedList(Node *head, Node *lastNode) { 
      if (head == NULL ) 
           return; 

      // if last two nodes and already sorted return 
      if (head == lastNode || head->next == lastNode) 
           return; 

      Node* nextNode = head->next; 
      if (nextNode->next == lastNode) 
      { 
           if (head->value < head->next->value) 
                     return; 
           else 
           { 
                swap(head, head->next); 
                return; 
           } 
      } 

      Node *pivot = head; 
      Node *startNode = head->next, *endNode = head->next, 
           *currSwapNode = startNode;

      while (1) { 
           while (startNode != lastNode) { 
                if (startNode->value < pivot->value) { 
                     currSwapNode = startNode; 
                     startNode = startNode->next; 
                } else { 
                     break; 
                } 
           } 

           if (startNode == lastNode) 
                break; 
           endNode = startNode == lastNode ? startNode : startNode->next; 

           while (endNode != lastNode && endNode->value >= pivot->value) { 
                endNode = endNode->next; 
           } 

           if (endNode != lastNode && startNode != lastNode) 
           { 
                swap(startNode, endNode); 
                currSwapNode = startNode; 
           } 
           else 
                break; 

           startNode = startNode->next; 
      } 

      if (currSwapNode != NULL && pivot->value > currSwapNode->value) { 
           swap(pivot, currSwapNode); 
           sortLinkedList(head, currSwapNode); 
           sortLinkedList(currSwapNode->next, lastNode); 
      } 
      else 
           sortLinkedList(currSwapNode, lastNode); 
 } 

 int main() { 
      int numNumbers, number, i; 
      Node *head = NULL, *current = NULL; 
      printf("Enter the numbers : "); 
      scanf("%d", &numNumbers); 

      for (i = 0; i < numNumbers; i++) { 
           scanf("%d", &number); 
           Node *node = malloc(sizeof(Node)); 
           node->value = number; 
           node->next = NULL; 
           if (current != NULL ) { 
                current->next = node; 
           } 

           if (head == NULL ) { 
                head = node; 
           } 
           current = node; 
      } 

      current = head; 
      while (current != NULL ) { 
           printf("%d ", current->value); 
           current = current->next; 
      } 

      printf("\n"); 
      sortLinkedList(head, NULL ); 

      current = head; 
      while (current != NULL ) { 
           printf("%d ", current->value); 
           current = current->next; 
      } 
      return 0; 
 } 

Find common elements in given two Binary Search Trees

 /*  
  * Two BST are given find common elements in both  
  * Algo works like this:  
  * Iteratively traverse both the tree in inorder fashion  
  * If the first tree node is less than the second tree move the  
  * first tree forward else if the second tree node is less than the  
  * first tree move second tree forward. If equal move both tree forward  
  * Do this operation till either one of the tree is complete.  
  *  
  */  
   
 void CommonElementsInBST(TreeNode* root1, TreeNode* root2) {  
      Stack *stack1 = createStack();  
      Stack *stack2 = createStack();  
      int commonElementCount = 0;  
   
      do {  
           while (root1 != NULL ) {  
                push(stack1, root1);  
                root1 = root1->left;  
           }  
           while (root2 != NULL ) {  
                push(stack2, root2);  
                root2 = root2->left;  
           }  
   
           if (isEmpty(stack1) != 0 && isEmpty(stack2)) {  
                root1 = (TreeNode*)top(stack1);  
                root2 = (TreeNode*)top(stack2);  
                if (*((int*)root1->object) < *((int*)root2->object)) {  
                     pop(stack1);  
                     root1 = root1->right;  
                } else if (*((int*)root1->object) > *((int*)root2->object)) {  
                     pop(stack2);  
                     root2 = root2->right;  
                } else {  
                     pop(stack1);  
                     pop(stack2);  
                     printf("%d ", *((int*) root1->object));  
                     root1 = root1->right;  
                     root2 = root2->right;  
                     commonElementCount++;  
                }  
           }  
      } while (((isEmpty(stack1) != 0) || root1 != NULL) && ((isEmpty(stack2) != 0) || root1 != NULL));  
      printf("Number of common elements are : %d", commonElementCount);  
 }  
   

Mirror a Binary Tree

Following algorithm would create a mirror of a Tree

 void mirror(TreeNode* root) { 
   if (root == NULL ) 
     return; 
  
   TreeNode* temp = root->left; 
   root->left = root->right; 
   root->right = temp; 
   mirror(root->left); 
   mirror(root->right); 
 } 

Removing consecutive Zeros

 
/*Remove all two consecutive zeros in the given string.

 Example: a3409jd00dk000d

 Output: a3409jddk000d

 Note: If there are less/more than two consecutive zeros, they should not be replaced.

 */



void remove2zeros(char *input) {
 char *temp = input;

 while (*temp != '\0') {
  if (*temp == '0' && *(temp - 1) != '0' && *(temp + 1) == '0'
    && *(temp + 2) != '0') {
   temp = temp + 2;
  } else {
   if (input != temp) {
    *input++ = *temp++;
   } else {
    temp++;
    input++;
   }
  }
 }
 *input = '\0';
}