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

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
}
 
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;
 
    if (head==NULL || head->arbit==NULL)
    {
        *list1 = head;
        *list2 = NULL;
        return;
    }
 
    slow = head,  fast = head->arbit;
 
    // 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.
   *list1 = head;
    *list2 = slow->arbit;
    slow->arbit = NULL;
}
 
 
//Main function, which will sort the list
void MergeSort(struct LLNode** head)
{
    struct LLNode* list1, *list2;
    if ((*head == NULL) || ((*head)->arbit == NULL))
    {
        return;
    }
    // Split list(head) into 'list1' and 'list2' sublists 
    SplitLL(*head, &list1, &list2);
 
    // Recursively sort the sublists 
    MergeSort(&list1);
    MergeSort(&list2);

    //merge the two sorted lists together
    *head = MergeSortedLists(list1, list2);
} 
//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
struct LLNode* ChangeArbitaryPTR(struct LLNode *head)
{
    //Copy next into arbitary for all nodes 
    struct LLNode *temp = head;
    while (temp != NULL)
    {
        temp->arbit = temp->next;
        temp = temp->next;
    }
    //Merge sort for aribitary pointers
    MergeSort(&head);
    return head;
}
 
//Main function
int main()
{
    //initial list has no elements
    struct LLNode* head = NULL;
    insertAtBeginning(&head,2);
    insertAtBeginning(&head,13);
    insertAtBeginning(&head,11);
    insertAtBeginning(&head,3);
 
    ChangeArbitaryPTR(head);
 
    cout<<"Final output: \n";
    display(head);
    return 0;
}
Try It

 


Next > < Prev
Scroll to Top