Point to Greatest Value Node

Easy

0/40

Average time to solve is 10m

Contributed by

23 upvotes

Asked in companies

Problem statement

You are given a singly linked list with every node having an additional “arbitrary” pointer that currently points to NULL. We need to make the “arbitrary” pointer to the greatest value node in a linked list on its right side.

More formally, each Linked List node has three attributes ‘data’, which is the value of the node, the ‘next’ pointer, which points to the next node, and an ‘arbit’ pointer which is initially NULL.

Note:

You need to return the head after populating the ‘arbit’ pointer.

For example:

Given ‘head’ as 3 -> 5 -> 2 -> 1.

After populating the arbitrary pointer, each node's ‘arbit’ pointer would point to 5 2 1 -1 respectively.

Detailed explanation ( Input/output format, Notes, Images )

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.

The second line of each test case contains space-separated integers, denoting the elements in linked list nodes, and -1 denotes the end of the linked list.

Output Format :

For each test case, print integers denoting the value of the nodes being pointed by the arbitrary pointer of that node, if the arbitrary pointer points to NULL, print -1.

Note:

You are supposed to return the head of the linked list, whose arbitrary pointer is populated.

You are not required to print the expected output; it has already been taken care of. Just implement the function.

Constraints:

1 <= ‘T’ <= 10
1 <= ‘N’ <= 5000
0 <= ‘data’ <= 10 ^ 4 and ‘data’ != -1

Time Limit: 1sec.

Sample Input 1 :

2
3 5 2 1 -1
1 3 5 7 -1

Sample Output 1 :

5 2 1 -1
7 7 7 -1

Explanation of the Sample Input 1:

For the first test case :

In the given Linked List, the above way will be how we populate the arbitrary pointer.

For the second test case:

In the given Linked List, the above way will be how we populate the arbitrary pointer.

Sample Input 2 :

2
4 3 2 1 -1
1 5 3 -1

Sample Output 2 :

3 2 1 -1
5 3 -1

Console