thecoderenroute

Final DS

Nov 14th, 2020
92
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 7.39 KB | None | 0 0
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <bits/stdc++.h>
  4.  
  5. // Data Structure to store a linked list Node
  6. struct Node
  7. {
  8.     int data;
  9.     struct Node *next;
  10. };
  11.  
  12. // Helper function to print given linked list
  13. void display(struct Node *head)
  14. {
  15.     printf("\n");
  16.     struct Node *ptr = head;
  17.     while (ptr)
  18.     {
  19.         printf("%d -> ", ptr->data);
  20.         ptr = ptr->next;
  21.     }
  22.  
  23.     printf("null");
  24. }
  25.  
  26. // Helper function to insert new Node in the beginning of the linked list
  27. void create(struct Node **head, int data)
  28. {
  29.     struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
  30.     newNode->data = data;
  31.     newNode->next = *head;
  32.     *head = newNode;
  33. }
  34.  
  35. // Remove duplicates from a sorted list
  36. void RemoveDuplicates(struct Node **head)
  37. {
  38.     // do nothing if the list is empty
  39.     if (head == NULL)
  40.         return;
  41.  
  42.     struct Node *current;
  43.     struct Node *current1 = *head;
  44.     // Compare current Node with next Node
  45.     while (current1->next != NULL)
  46.     {
  47.         current = current1;
  48.         // printf("\nhere current1 is %d and current is %d", current1->data, current->data);
  49.         while ((current)->next != NULL)
  50.         {
  51.             // printf("\nhere current is %d and current1 is %d and current1-> next is %d",current->data, current1->data, current1->next->data);
  52.             if (current1->data == current->next->data)
  53.             {
  54.                 // printf("\ndeleting: %d because of %d", current->data, current1->data);
  55.                 struct Node *nextNext = current->next->next;
  56.                 free((current)->next);
  57.                 current->next = nextNext;
  58.             }
  59.             else
  60.             {
  61.                 current = current->next; // only advance if no deletion
  62.             }
  63.         }
  64.         // printf("\n\n and head is %d and current1->next is %d yep", (*head)->data, current1->next->data);
  65.         current1 = current1->next;
  66.     }
  67. }
  68.  
  69. //Represent a Node of the singly linked list
  70.  
  71. //reverseList() will reverse the singly linked list and return the head of the list
  72. struct Node *reverseList(struct Node *temp)
  73. {
  74.     struct Node *current = temp;
  75.     struct Node *prevNode = NULL, *nextNode = NULL;
  76.  
  77.     //Swap the previous and next Nodes of each Node to reverse the direction of the list
  78.     while (current != NULL)
  79.     {
  80.         nextNode = current->next;
  81.         current->next = prevNode;
  82.         prevNode = current;
  83.         current = nextNode;
  84.     }
  85.     return prevNode;
  86. }
  87.  
  88. //isPalindrome() will determine whether given list is palindrome or not.
  89. void isPalindrome(struct Node *head)
  90. {
  91.     struct Node *current = head;
  92.     bool flag = true;
  93.  
  94.     //Store the mid position of the list
  95.     int mid = (size % 2 == 0) ? (size / 2) : ((size + 1) / 2);
  96.  
  97.     //Finds the middle Node in given singly linked list
  98.     for (int i = 1; i < mid; i++)
  99.     {
  100.         current = current->next;
  101.     }
  102.  
  103.     //Reverse the list after middle Node to end
  104.     struct Node *revHead = reverseList(current->next);
  105.  
  106.     //Compare Nodes of first half and second half of list
  107.     while (head != NULL && revHead != NULL)
  108.     {
  109.         if (head->data != revHead->data)
  110.         {
  111.             flag = false;
  112.             break;
  113.         }
  114.         head = head->next;
  115.         revHead = revHead->next;
  116.     }
  117.  
  118.     if (flag)
  119.         printf("Given singly linked list is a palindrome\n");
  120.     else
  121.         printf("Given singly linked list is not a palindrome\n");
  122. }
  123. void sortList(struct Node **head)
  124. {
  125.     //Node current will point to head
  126.     struct Node *current = *head, *index = NULL;
  127.     int temp;
  128.  
  129.     if (head == NULL)
  130.     {
  131.         return;
  132.     }
  133.     else
  134.     {
  135.         while (current != NULL)
  136.         {
  137.             //Node index will point to Node next to current
  138.             index = current->next;
  139.  
  140.             while (index != NULL)
  141.             {
  142.                 //If current Node's data is greater than index's Node data, swap the data between them
  143.                 if (current->data > index->data)
  144.                 {
  145.                     temp = current->data;
  146.                     current->data = index->data;
  147.                     index->data = temp;
  148.                 }
  149.                 index = index->next;
  150.             }
  151.             current = current->next;
  152.         }
  153.     }
  154. }
  155.  
  156. struct Node *rearrange(struct Node *top, int count)
  157. {
  158.  
  159.     struct Node *temp1, *prev, *after;
  160.  
  161.     temp1 = top->next;
  162.     prev = top;
  163.     after = top->next;
  164.  
  165.     while (count % 2 != 0)
  166.     {
  167.         prev->next = after->next;
  168.         prev = prev->next;
  169.         after->next = prev->next;
  170.         if (after->next == NULL)
  171.         {
  172.             break;
  173.         }
  174.         else
  175.         {
  176.             after = after->next;
  177.         }
  178.     }
  179.     prev->next = temp1;
  180.  
  181.     while (count % 2 == 0)
  182.     {
  183.  
  184.         prev->next = after->next;
  185.         if (prev->next == NULL)
  186.         {
  187.             break;
  188.         }
  189.         else
  190.         {
  191.             prev = prev->next;
  192.         }
  193.         after->next = prev->next;
  194.  
  195.         after = after->next;
  196.     }
  197.     prev->next = temp1;
  198.     return top;
  199. }
  200.  
  201. // deleting n nodes after every m nodes
  202. void deleteInMass(struct node **p, int n, int m)
  203. {
  204.  
  205.     cout << "n is " << n << " and m is" << m;
  206.     int index = 0;
  207.     struct node *t = *p;
  208.  
  209.     if (n == 0)
  210.     {
  211.         return;
  212.     }
  213.     if (m == 0)
  214.     {
  215.         (*p) = NULL;
  216.         return;
  217.     }
  218.  
  219.     while (t != NULL)
  220.     {
  221.         int nCount = 0;
  222.         int mCount = 1;
  223.         cout << "\nHere, t is at " << t->data;
  224.         while (mCount < m)
  225.         {
  226.             cout << "\nKeeping " << t->data << " When Mc is " << mCount;
  227.             t = t->link;
  228.             mCount++;
  229.             if (t == NULL)
  230.             {
  231.                 goto finit;
  232.             }
  233.             if (mCount >= m)
  234.             {
  235.                 printf("\nbreaking at mC=5d", mCount);
  236.                 break;
  237.             }
  238.         }
  239.  
  240.         struct node *t1 = t;
  241.         t1 = t1->link;
  242.         while (1)
  243.         {
  244.             if (t1 == NULL)
  245.             {
  246.                 t->link == NULL;
  247.                 goto finit;
  248.             }
  249.             struct node *temp = t1;
  250.             cout << "\nDeleting: " << temp->data;
  251.             t1 = t1->link;
  252.             free(temp);
  253.             nCount++;
  254.             if (nCount >= n)
  255.             {
  256.                 break;
  257.             }
  258.         }
  259.         t->link = t1;
  260.         t = t->link;
  261.         if (t == NULL)
  262.         {
  263.             break;
  264.         }
  265.         printf("\nt is at ", t->data);
  266.         printf("\nAfter deletion: ");
  267.         display(*p);
  268.     }
  269. finit:;
  270. }
  271.  
  272. // main method
  273. int main()
  274. {
  275.     // input keys
  276.  
  277.     int num, op, count = 0;
  278.     struct Node *head = NULL;
  279.  
  280.     do
  281.     {
  282.         printf("\nMENU\n1.Create list\n2.Display list\n3.Remove duplicates\n4.Check Pallindrome\n5.Sort\n6.Rearrange\n7. Deleting n nodes after every m\n0.Exit\n");
  283.         scanf("%d", &op);
  284.         switch (op)
  285.         {
  286.         case 0:
  287.             break;
  288.         case 1:
  289.             printf("Enter the number you want to insert:");
  290.             count++;
  291.  
  292.             scanf("%d", &num);
  293.             create(&head, num);
  294.             break;
  295.         case 2:
  296.             display(head);
  297.             break;
  298.         case 3:
  299.             RemoveDuplicates(&head);
  300.             break;
  301.         case 4:
  302.             isPalindrome(head);
  303.             break;
  304.         case 5:
  305.             sortList(&head);
  306.             break;
  307.         case 6:
  308.             rearrange(head, count);
  309.             break;
  310.         case 7:
  311.             int n, m;
  312.             printf("\nEnter n: ");
  313.             scanf("%d", &n);
  314.             printf("Enter m: ");
  315.             scanf("%d", &m);
  316.             deleteInMass(&head, n, m)
  317.         }
  318.     } while (op != 0);
  319.  
  320.     return 0;
  321. }
Advertisement
Add Comment
Please, Sign In to add comment