Point to next higher value node in a linked list with an arbitrary pointer - GeeksforGeeks
Given singly linked list with every node having an additional "arbitrary" pointer that currently points to NULL. Need to make the "arbitrary" pointer point to the next higher value node.
An Efficient Solution works in O(nLogn) time. The idea is to use Merge Sort for linked list.
1) Traverse input list and copy next pointer to arbit pointer for every node.
2) Do Merge Sort for the linked list formed by arbit pointers.
Read full article from Point to next higher value node in a linked list with an arbitrary pointer - GeeksforGeeks
Given singly linked list with every node having an additional "arbitrary" pointer that currently points to NULL. Need to make the "arbitrary" pointer point to the next higher value node.
An Efficient Solution works in O(nLogn) time. The idea is to use Merge Sort for linked list.
1) Traverse input list and copy next pointer to arbit pointer for every node.
2) Do Merge Sort for the linked list formed by arbit pointers.
struct node* populateArbit(struct node *head){ // Copy next pointers to arbit pointers struct node *temp = head; while (temp != NULL) { temp->arbit = temp->next; temp = temp->next; } // Do merge sort for arbitrary pointers MergeSort(&head); // Return head of arbitrary pointer linked list return head;}/* sorts the linked list formed by arbit pointers (does not change next pointer or data) */void MergeSort(struct node** headRef){ struct node* head = *headRef; struct node* a, *b; /* Base case -- length 0 or 1 */ if ((head == NULL) || (head->arbit == NULL)) return; /* Split head into 'a' and 'b' sublists */ FrontBackSplit(head, &a, &b); /* Recursively sort the sublists */ MergeSort(&a); MergeSort(&b); /* answer = merge the two sorted lists together */ *headRef = SortedMerge(a, b);}/* See http://geeksforgeeks.org/?p=3622 for details of this function */struct node* SortedMerge(struct node* a, struct node* b){ struct 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->arbit = SortedMerge(a->arbit, b); } else { result = b; result->arbit = SortedMerge(a, b->arbit); } return (result);}/* 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(struct node* source, struct node** frontRef, struct node** backRef){ struct node* fast, *slow; if (source==NULL || source->arbit==NULL) { /* length < 2 cases */ *frontRef = source; *backRef = NULL; return; } slow = source, fast = source->arbit; /* Advance 'fast' two nodes, and advance 'slow' one node */ while (fast != NULL) { fast = fast->arbit; if (fast != NULL) { slow = slow->arbit; fast = fast->arbit; } } /* 'slow' is before the midpoint in the list, so split it in two at that point. */ *frontRef = source; *backRef = slow->arbit; slow->arbit = NULL;}