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->next= *head;
    curr->arbit = NULL;
    *head = curr;
        //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
    head = ReverseLL(head);
    // 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
   //return head
   return ReverseLL(head);
}
 
//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;
    insertAtBeginning(&head,7);
    insertAtBeginning(&head,11);
    insertAtBeginning(&head,13);
    insertAtBeginning(&head,6);
 
    head = ChangeArbitaryPTR(head);
 
    cout<<"Final output:\n";
    display(head);
 
    return 0;
}
Try It

 


Next > < Prev
Scroll to Top