Given a linked list containing n nodes. The problem is to rearrange the nodes of the list in such a way that the data in first node is first minimum, second node is first maximum, third node is second minimum, fourth node is second maximum and so on.
Examples:
Input : list: 4->1->3->5->2 Output : 1->5->2->4->3 Input : list: 10->9->8->7->6->5 Output : 5->10->6->9->7->8
Approach: Following are the steps:
- Sort the linked list using Merge Sort technique.
- Split the list into front and back lists. Refer FrontBackProcedure of this post.
- Now, reverse the back list. Refer this post.
- Finally, merge the nodes of first and back lists in alternate order.
Implementation
CPP
// C++ implementation of alternative sorting// of the Linked list#include <bits/stdc++.h>using namespace std;// node of a linked liststruct Node { int data; struct Node* next;};// function to get a new nodeNode* getNode(int data){ // allocate space for node Node* newNode = (Node*)malloc(sizeof(Node)); // put in the data newNode->data = data; newNode->next = NULL; return newNode;}// Split the nodes of the given list into front and// back halves, and return the two lists using the// reference parameters. If the length is odd, the// extra node should go in the front list. Uses the// fast/slow pointer strategy.void FrontBackSplit(Node* source, Node** frontRef, Node** backRef){ Node* fast; Node* slow; if (source == NULL || source->next == NULL) { // length < 2 cases *frontRef = source; *backRef = NULL; } else { slow = source; fast = source->next; // Advance 'fast' two nodes, and // advance 'slow' one node while (fast != NULL) { fast = fast->next; if (fast != NULL) { slow = slow->next; fast = fast->next; } } // 'slow' is before the midpoint in the list, // so split it in two at that point. *frontRef = source; *backRef = slow->next; slow->next = NULL; }}// function to merge two sorted lists in// sorted orderNode* SortedMerge(Node* a, Node* b){ Node* result = NULL; // Base cases if (a == NULL) return b; else if (b == NULL) return a; // Pick either a or b, and recur if (a->data <= b->data) { result = a; result->next = SortedMerge(a->next, b); } else { result = b; result->next = SortedMerge(a, b->next); } return result;}// sorts the linked list by changing// next pointers (not data)void MergeSort(Node** headRef){ Node* head = *headRef; Node *a, *b; // Base case -- length 0 or 1 if ((head == NULL) || (head->next == NULL)) return; // Split head into 'a' and 'b' sublists FrontBackSplit(head, &a, &b); // Recursively sort the sublists MergeSort(&a); MergeSort(&b); // merge the two sorted lists together *headRef = SortedMerge(a, b);}// function to reverse the linked liststatic void reverse(Node** head_ref){ Node* prev = NULL; Node* current = *head_ref; Node* next; while (current != NULL) { next = current->next; current->next = prev; prev = current; current = next; } *head_ref = prev;}// function to alternately merge two listsvoid alternateMerge(Node* head1, Node* head2){ Node *p, *q; while (head1 != NULL && head2 != NULL) { // merging nodes alternately by // making the desired links p = head1->next; head1->next = head2; head1 = p; q = head2->next; head2->next = head1; head2 = q; }}// function for alternative sort of the// linked listNode* altSortForLinkedList(Node* head){ // sort the linked list MergeSort(&head); Node *front, *back; // Split head into 'front' and 'back' sublists FrontBackSplit(head, &front, &back); // reversing the 'back' list reverse(&back); // merging the nodes of 'front' and 'back' // lists alternately alternateMerge(front, back); // required head of final list return front;}// Function to print nodes in// a given linked listvoid printList(Node* head){ while (head != NULL) { cout << head->data << " "; head = head->next; }}// Driver program to test aboveint main(){ // linked list: 10->9->8->7->6->5 Node* head = getNode(10); head->next = getNode(9); head->next->next = getNode(8); head->next->next->next = getNode(7); head->next->next->next->next = getNode(6); head->next->next->next->next->next = getNode(5); cout << "Original list: "; printList(head); head = altSortForLinkedList(head); cout << "\nModified list: "; printList(head); return 0;} |
Output
Original list: 10 9 8 7 6 5 Modified list: 5 10 6 9 7 8
Time Complexity: O(n*logn).
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
