# Point to next higher value node

## In the given linked list, every node has an additional pointer (arbitrary ptr) that points to NULL. We need to write an algorithm to change this arbitrary pointer to next higher value node.

### Example

Time complexity : O(nlogn)

## Algorithm

We use Merge sort of linked list here,

a. Traverse the input linked list and copy next pointer for every node.

b. Merge sort the linked list formed by arbitrary pointers.

c. Use display function to display LL formed by next pointers and arbitrary pointers.

MergeSort ()

1. If head is NULL or there is only one element in the linked list then return

2. Else divide the linked list into two halves ,SplitLL() splits list into list1 and list2

3. Sort the two halvesie, recursively call MergeSort(list1), MergeSort(list2)

4. Merge the two sorted halves ie, MergeSortedLists(list1,list2).

## C++ Program

``````#include <bits/stdc++.h>

using namespace std;

struct LLNode{
int data;
struct LLNode *next, *arbit;
};

{
struct LLNode *curr = new LLNode;
//make list1 new node with this data and next pointing to NULL
curr->data=dataToBeInserted;
curr->arbit = NULL;
//O(1) constant time
}

struct LLNode* MergeSortedLists(struct LLNode* list1, struct LLNode* list2)
{
struct LLNode* result = NULL;

/* Base cases */
if (list1 == NULL)
return (list2);
else if (list2==NULL)
return (list1);

/* Pick either list1 or list2, and recur */
if (list1->data <= list2->data)
{
result = list1;
result->arbit = MergeSortedLists(list1->arbit, list2);
}
else
{
result = list2;
result->arbit = MergeSortedLists(list1, list2->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 SplitLL(struct LLNode* head, struct LLNode** list1, struct LLNode** list2)
{
struct LLNode* fast, *slow;

{
*list2 = NULL;
return;
}

// Move 'fast' two nodes, and move '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.
*list2 = slow->arbit;
slow->arbit = NULL;
}

//Main function, which will sort the list
{
struct LLNode* list1, *list2;
{
return;
}
// Split list(head) into 'list1' and 'list2' sublists

// Recursively sort the sublists
MergeSort(&list1);
MergeSort(&list2);

//merge the two sorted lists together
}
//Print LL with next and arbitary pointer values
void display(LLNode *node)
{
cout<<"LLNode\t   Next Pointer\t   Arbitrary Pointer\n";
while (node!=NULL)
{
cout<<node->data<<"\t\t";
if (node->next)
{
cout<<node->next->data<<"\t\t";
}
else
{
cout<<"NULL"<<"\t\t";
}
if (node->arbit)
{
cout << node->arbit->data;
}
else
{
cout << "NULL";
}
cout << endl;
node = node->next;
}
}

//function to change arbitary pointers
{
//Copy next into arbitary for all nodes
while (temp != NULL)
{
temp->arbit = temp->next;
temp = temp->next;
}
//Merge sort for aribitary pointers
}

//Main function
int main()
{
//initial list has no elements