thecoderenroute

Final DS Project

Nov 13th, 2020
71
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 6.98 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. //Represent the head and tail of the singly linked list
  72. struct Node *head, *tail = NULL;
  73. int size = 0;
  74.  
  75. //addNode() will add a new Node to the list
  76. // void addNode(int data) {
  77. //     //Create a new Node
  78. //     struct Node newNode = (struct Node)malloc(sizeof(struct Node));
  79. //     newNode->data = data;
  80. //     newNode->next = NULL;
  81.  
  82. //     //Checks if the list is empty
  83. //     if(head == NULL) {
  84. //         //If list is empty, both head and tail will point to new Node
  85. //         head = newNode;
  86. //         tail = newNode;
  87. //     }
  88. //     else {
  89. //         //newNode will be added after tail such that tail's next will point to newNode
  90. //         tail->next = newNode;
  91. //         //newNode will become new tail of the list
  92. //         tail = newNode;
  93. //     }
  94. //     //Size will count the number of Nodes present in the list
  95. //     size++;
  96. // }
  97.  
  98. //reverseList() will reverse the singly linked list and return the head of the list
  99. struct Node *reverseList(struct Node *temp)
  100. {
  101.     struct Node *current = temp;
  102.     struct Node *prevNode = NULL, *nextNode = NULL;
  103.  
  104.     //Swap the previous and next Nodes of each Node to reverse the direction of the list
  105.     while (current != NULL)
  106.     {
  107.         nextNode = current->next;
  108.         current->next = prevNode;
  109.         prevNode = current;
  110.         current = nextNode;
  111.     }
  112.     return prevNode;
  113. }
  114.  
  115. //isPalindrome() will determine whether given list is palindrome or not.
  116. void isPalindrome(struct Node *head)
  117. {
  118.     struct Node *current = head;
  119.     bool flag = true;
  120.  
  121.     //Store the mid position of the list
  122.     int mid = (size % 2 == 0) ? (size / 2) : ((size + 1) / 2);
  123.  
  124.     //Finds the middle Node in given singly linked list
  125.     for (int i = 1; i < mid; i++)
  126.     {
  127.         current = current->next;
  128.     }
  129.  
  130.     //Reverse the list after middle Node to end
  131.     struct Node *revHead = reverseList(current->next);
  132.  
  133.     //Compare Nodes of first half and second half of list
  134.     while (head != NULL && revHead != NULL)
  135.     {
  136.         if (head->data != revHead->data)
  137.         {
  138.             flag = false;
  139.             break;
  140.         }
  141.         head = head->next;
  142.         revHead = revHead->next;
  143.     }
  144.  
  145.     if (flag)
  146.         printf("Given singly linked list is a palindrome\n");
  147.     else
  148.         printf("Given singly linked list is not a palindrome\n");
  149. }
  150. void sortList(struct Node **head)
  151. {
  152.     //Node current will point to head
  153.     struct Node *current = *head, *index = NULL;
  154.     int temp;
  155.  
  156.     if (head == NULL)
  157.     {
  158.         return;
  159.     }
  160.     else
  161.     {
  162.         while (current != NULL)
  163.         {
  164.             //Node index will point to Node next to current
  165.             index = current->next;
  166.  
  167.             while (index != NULL)
  168.             {
  169.                 //If current Node's data is greater than index's Node data, swap the data between them
  170.                 if (current->data > index->data)
  171.                 {
  172.                     temp = current->data;
  173.                     current->data = index->data;
  174.                     index->data = temp;
  175.                 }
  176.                 index = index->next;
  177.             }
  178.             current = current->next;
  179.         }
  180.     }
  181. }
  182.  
  183. struct Node *rearrange(struct Node *top, int count)
  184. {
  185.  
  186.     struct Node *temp1, *prev, *after;
  187.  
  188.     temp1 = top->next;
  189.     prev = top;
  190.     after = top->next;
  191.  
  192.     while (count % 2 != 0)
  193.     {
  194.         prev->next = after->next;
  195.         prev = prev->next;
  196.         after->next = prev->next;
  197.         if (after->next == NULL)
  198.         {
  199.             break;
  200.         }
  201.         else
  202.         {
  203.             after = after->next;
  204.         }
  205.     }
  206.     prev->next = temp1;
  207.  
  208.     while (count % 2 == 0)
  209.     {
  210.  
  211.         prev->next = after->next;
  212.         if (prev->next == NULL)
  213.         {
  214.             break;
  215.         }
  216.         else
  217.         {
  218.             prev = prev->next;
  219.         }
  220.         after->next = prev->next;
  221.  
  222.         after = after->next;
  223.     }
  224.     prev->next = temp1;
  225.     return top;
  226. }
  227.  
  228. //display() will display all the Nodes present in the list
  229. void display()
  230. {
  231.     //Node current will point to head
  232.     struct Node *current = head;
  233.  
  234.     if (head == NULL)
  235.     {
  236.         printf("List is empty\n");
  237.         return;
  238.     }
  239.     printf("Nodes of singly linked list: \n");
  240.     while (current != NULL)
  241.     {
  242.         //Prints each Node by incrementing pointer
  243.         printf("%d ", current->data);
  244.         current = current->next;
  245.     }
  246.     printf("\n");
  247. }
  248.  
  249. // main method
  250. int main()
  251. {
  252.     // input keys
  253.  
  254.  
  255.     int num, op, count = 0;
  256.     struct Node *head = NULL;
  257.     do
  258.     {
  259.         printf("\nMENU\n1.Create list\n2.Display list\n3.Remove duplicates\n4.Check Pallindrome\n5.sort\n6.rearrange\n");
  260.         scanf("%d", &op);
  261.         switch (op)
  262.         {
  263.         case 0:
  264.             break;
  265.         case 1:
  266.             printf("Enter the number you want to insert:");
  267.             count++;
  268.  
  269.             scanf("%d", &num);
  270.             create(&head, num);
  271.             break;
  272.         case 2:
  273.             display(head);
  274.             break;
  275.         case 3:
  276.             RemoveDuplicates(&head);
  277.             break;
  278.         case 4:
  279.             isPalindrome(head);
  280.             break;
  281.         case 5:
  282.             sortList(&head);
  283.             break;
  284.         case 6:
  285.             rearrange(head, count);
  286.         }
  287.     } while (op != 0);
  288.  
  289.     return 0;
  290. }
Advertisement
Add Comment
Please, Sign In to add comment