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;
}