Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <stdlib.h>
- #include <bits/stdc++.h>
- // Data Structure to store a linked list Node
- struct Node
- {
- int data;
- struct Node *next;
- };
- // Helper function to print given linked list
- void display(struct Node *head)
- {
- printf("\n");
- struct Node *ptr = head;
- while (ptr)
- {
- printf("%d -> ", ptr->data);
- ptr = ptr->next;
- }
- printf("null");
- }
- // Helper function to insert new Node in the beginning of the linked list
- void create(struct Node **head, int data)
- {
- struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
- newNode->data = data;
- newNode->next = *head;
- *head = newNode;
- }
- // Remove duplicates from a sorted list
- void RemoveDuplicates(struct Node **head)
- {
- // do nothing if the list is empty
- if (head == NULL)
- return;
- struct Node *current;
- struct Node *current1 = *head;
- // Compare current Node with next Node
- while (current1->next != NULL)
- {
- current = current1;
- // printf("\nhere current1 is %d and current is %d", current1->data, current->data);
- while ((current)->next != NULL)
- {
- // printf("\nhere current is %d and current1 is %d and current1-> next is %d",current->data, current1->data, current1->next->data);
- if (current1->data == current->next->data)
- {
- // printf("\ndeleting: %d because of %d", current->data, current1->data);
- struct Node *nextNext = current->next->next;
- free((current)->next);
- current->next = nextNext;
- }
- else
- {
- current = current->next; // only advance if no deletion
- }
- }
- // printf("\n\n and head is %d and current1->next is %d yep", (*head)->data, current1->next->data);
- current1 = current1->next;
- }
- }
- //Represent a Node of the singly linked list
- //reverseList() will reverse the singly linked list and return the head of the list
- struct Node *reverseList(struct Node *temp)
- {
- struct Node *current = temp;
- struct Node *prevNode = NULL, *nextNode = NULL;
- //Swap the previous and next Nodes of each Node to reverse the direction of the list
- while (current != NULL)
- {
- nextNode = current->next;
- current->next = prevNode;
- prevNode = current;
- current = nextNode;
- }
- return prevNode;
- }
- //isPalindrome() will determine whether given list is palindrome or not.
- void isPalindrome(struct Node *head)
- {
- struct Node *current = head;
- bool flag = true;
- //Store the mid position of the list
- int mid = (size % 2 == 0) ? (size / 2) : ((size + 1) / 2);
- //Finds the middle Node in given singly linked list
- for (int i = 1; i < mid; i++)
- {
- current = current->next;
- }
- //Reverse the list after middle Node to end
- struct Node *revHead = reverseList(current->next);
- //Compare Nodes of first half and second half of list
- while (head != NULL && revHead != NULL)
- {
- if (head->data != revHead->data)
- {
- flag = false;
- break;
- }
- head = head->next;
- revHead = revHead->next;
- }
- if (flag)
- printf("Given singly linked list is a palindrome\n");
- else
- printf("Given singly linked list is not a palindrome\n");
- }
- void sortList(struct Node **head)
- {
- //Node current will point to head
- struct Node *current = *head, *index = NULL;
- int temp;
- if (head == NULL)
- {
- return;
- }
- else
- {
- while (current != NULL)
- {
- //Node index will point to Node next to current
- index = current->next;
- while (index != NULL)
- {
- //If current Node's data is greater than index's Node data, swap the data between them
- if (current->data > index->data)
- {
- temp = current->data;
- current->data = index->data;
- index->data = temp;
- }
- index = index->next;
- }
- current = current->next;
- }
- }
- }
- struct Node *rearrange(struct Node *top, int count)
- {
- struct Node *temp1, *prev, *after;
- temp1 = top->next;
- prev = top;
- after = top->next;
- while (count % 2 != 0)
- {
- prev->next = after->next;
- prev = prev->next;
- after->next = prev->next;
- if (after->next == NULL)
- {
- break;
- }
- else
- {
- after = after->next;
- }
- }
- prev->next = temp1;
- while (count % 2 == 0)
- {
- prev->next = after->next;
- if (prev->next == NULL)
- {
- break;
- }
- else
- {
- prev = prev->next;
- }
- after->next = prev->next;
- after = after->next;
- }
- prev->next = temp1;
- return top;
- }
- // deleting n nodes after every m nodes
- void deleteInMass(struct node **p, int n, int m)
- {
- cout << "n is " << n << " and m is" << m;
- int index = 0;
- struct node *t = *p;
- if (n == 0)
- {
- return;
- }
- if (m == 0)
- {
- (*p) = NULL;
- return;
- }
- while (t != NULL)
- {
- int nCount = 0;
- int mCount = 1;
- cout << "\nHere, t is at " << t->data;
- while (mCount < m)
- {
- cout << "\nKeeping " << t->data << " When Mc is " << mCount;
- t = t->link;
- mCount++;
- if (t == NULL)
- {
- goto finit;
- }
- if (mCount >= m)
- {
- printf("\nbreaking at mC=5d", mCount);
- break;
- }
- }
- struct node *t1 = t;
- t1 = t1->link;
- while (1)
- {
- if (t1 == NULL)
- {
- t->link == NULL;
- goto finit;
- }
- struct node *temp = t1;
- cout << "\nDeleting: " << temp->data;
- t1 = t1->link;
- free(temp);
- nCount++;
- if (nCount >= n)
- {
- break;
- }
- }
- t->link = t1;
- t = t->link;
- if (t == NULL)
- {
- break;
- }
- printf("\nt is at ", t->data);
- printf("\nAfter deletion: ");
- display(*p);
- }
- finit:;
- }
- // main method
- int main()
- {
- // input keys
- int num, op, count = 0;
- struct Node *head = NULL;
- do
- {
- 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");
- scanf("%d", &op);
- switch (op)
- {
- case 0:
- break;
- case 1:
- printf("Enter the number you want to insert:");
- count++;
- scanf("%d", &num);
- create(&head, num);
- break;
- case 2:
- display(head);
- break;
- case 3:
- RemoveDuplicates(&head);
- break;
- case 4:
- isPalindrome(head);
- break;
- case 5:
- sortList(&head);
- break;
- case 6:
- rearrange(head, count);
- break;
- case 7:
- int n, m;
- printf("\nEnter n: ");
- scanf("%d", &n);
- printf("Enter m: ");
- scanf("%d", &m);
- deleteInMass(&head, n, m)
- }
- } while (op != 0);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment