# Point to greatest value in the right

## 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 greatest node in the right side of current node.

### Example

Time complexity : O(n)

## Algorithm

a. Reverse the given linked list.

b. Keep track of maximum element so for while traversing.

c. Make arbitrary of every node to point to maximum. And update maximum value if current is more than maximum.

d. Reverse the modified linked list and return head.

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

## C++ Program

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

using namespace std;

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

void insertAtBeginning(struct LLNode**head, int dataToBeInserted)
{
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
}

//Reverse LL
struct LLNode* ReverseLL(struct LLNode *head)
{
struct LLNode *prev = NULL, *current = head, *next;
while (current != NULL)
{
next  = current->next;
current->next = prev;
prev = current;
current = next;
}
return prev;
}

//function to change pointer
struct LLNode* ChangeArbitaryPTR(struct LLNode *head)
{
// Reverse given linked list
// Initialize pointer to maximum value node
struct LLNode *max = head;
// Traverse the reversed list
struct LLNode *temp = head->next;
//update arbit pointer with max
//update max if requires
while (temp != NULL)
{
temp->arbit = max;
if (max->data < temp->data)
{
max = temp;
}
temp = temp->next;
}
//reverse the final LL to get original
}

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

//Main function
int main()
{
//initial list has no elements
struct LLNode* head = NULL;