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
- //Represent the head and tail of the singly linked list
- struct Node *head, *tail = NULL;
- int size = 0;
- //addNode() will add a new Node to the list
- // void addNode(int data) {
- // //Create a new Node
- // struct Node newNode = (struct Node)malloc(sizeof(struct Node));
- // newNode->data = data;
- // newNode->next = NULL;
- // //Checks if the list is empty
- // if(head == NULL) {
- // //If list is empty, both head and tail will point to new Node
- // head = newNode;
- // tail = newNode;
- // }
- // else {
- // //newNode will be added after tail such that tail's next will point to newNode
- // tail->next = newNode;
- // //newNode will become new tail of the list
- // tail = newNode;
- // }
- // //Size will count the number of Nodes present in the list
- // size++;
- // }
- //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;
- }
- //display() will display all the Nodes present in the list
- void display()
- {
- //Node current will point to head
- struct Node *current = head;
- if (head == NULL)
- {
- printf("List is empty\n");
- return;
- }
- printf("Nodes of singly linked list: \n");
- while (current != NULL)
- {
- //Prints each Node by incrementing pointer
- printf("%d ", current->data);
- current = current->next;
- }
- printf("\n");
- }
- // 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\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);
- }
- } while (op != 0);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment