Problem Description:
Sort the given doubly linked list using quicksort. Just complete the partition function using quicksort techniquetry to solve it in O(1) space .
Input:
In this problem, method takes two argument: the node1 and node2. The function should not read any input from stdin/console.
The struct Node has a data part which stores the data and a next pointer which points to the next element of the linked list.
There are multiple test cases. For each test case, this method will be called individually.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 |
/* a node of the doubly linked list */ /*struct node { int data; struct node *next; struct node *prev; }; struct node *lastNode(node *root) { while (root && root->next) root = root->next; return root; } void _quickSort(struct node* l, struct node *h) { if (h != NULL && l != h && l != h->next) { struct node *p = partition(l, h); _quickSort(l, p->prev); _quickSort(p->next, h); } } void quickSort(struct node *head) { // Find last node struct node *h = lastNode(head); // Call the recursive QuickSort _quickSort(head, h); }*/ node* partition(node *l, node *h){ //Your code goes here node *pvt=h; node *lft=l,*rit=h->prev; int tmp; int lVal=lft->data; int rVal=rit->data; int pVal=pvt->data; bool f=0; while(1) { while(lft!=h) { if(lft->data>pVal) break; lft=lft->next; } if(lft==h) break; while(lft!=rit) { if(rit->data<=pVal) break; rit=rit->prev; } if(lft==rit) break; tmp=rit->data; rit->data=lft->data; lft->data=tmp; } tmp=pvt->data; pvt->data=lft->data; lft->data=tmp; return lft; } |