1.
Introduction
2.
Problem Statement
2.1.
Example
3.
Intuition
4.
Complexity Analysis
4.1.
Time Complexity
5.
5.1.
How is the linked list represented in memory?
5.2.
How is the linked list different from the array?
5.3.
How do we check for palindromes in a linked list?
5.4.
Are linked lists (FIFO) or (LIFO)?
5.5.
Why are linked lists used over arrays?
6.
Conclusion
Last Updated: Mar 27, 2024

Point arbitrary pointer to greatest value right side node in a Linked List

Introduction

One of the most crucial things to understand while preparing for interviews is the linked list. Knowing how to use a linked list effectively may be quite beneficial in coding interviews. A linked list is a linear collection of data components whose order is determined by their physical location in memory rather than by their physical order. Instead, each piece serves as a stepping stone to the next. It's a data structure made up of a number of nodes that together form a sequence.

Problem Statement

Given a linked list with an extra arbitrary reference pointing to NULL at the start of each node. That arbitrary pointer must point to the node with the highest value on the right side of that node.

Intuition

The problem statement is simple: we will be given a singly linked list in which, in addition to the next pointer, there will be an arbit pointer that will be NULL at first, and we must make that arbit pointer refer to the biggest value in the right portion of the list.

A simple solution is to go through each node one at a time. Change the next pointer to the node with the largest value on the right side for each node. This solution has an O time complexity (n2).

In O(n) time, an Efficient Solution may complete its task. The steps are outlined below.

1. Reverse the linked list you've been given.
2. Begin traversing the linked list and record the highest value node you've come across so far. Make every node's arbit point to the maximum. Update max if the data in the current node exceeds the max node thus far.

Letâ€™s look at how we can implement this solution.

``````#include<bits/stdc++.h>
using namespace std;

struct Node
{
int val;
Node* next, *arbit;
};

// Create a new node with given data
Node *newNode(int data)
{
Node *new_node = new Node;
new_node->val = data;
new_node->next = NULL;
return new_node;
}

{
Node *prev = NULL, *current = head, *next;
while (current != NULL)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
}
return prev;
}

// Change arbit pointer in every node to the greatest value to its right.
{

// Traverse the reversed list
while (temp != NULL)
{
// Connect max through arbit pointer
temp->arbit = max;

// Update max if required
if (max->val < temp->val)
max = temp;

temp = temp->next;
}

}

// Function to print result linked list
{
cout<<"(Node, Next Pointer, Arbit Pointer)"<<endl;
while (node!=NULL)
{
cout <<"("<< node->val << ",";

if (node->next)
cout << node->next->val << ",";
else cout << "NULL" << ",";

if (node->arbit)
cout << node->arbit->val;
else cout << "NULL";

cout <<")";
cout << endl;

node = node->next;
}
}

int main()
{

return 0;
}``````

Output:

(Node, Next Pointer, Arbit Pointer)

(15,12,12)

(12,8,10)

(8,10,10)

(10,NULL,NULL)

Complexity Analysis

Time Complexity

O(n), where n is the number of linked list nodes. We have reversed the linked list 2 times and iterated the linked list to append the arbit pointer. Which results in the time complexity of order of O(n).

Also see, Rabin Karp Algorithm

How is the linked list represented in memory?

The linked list is kept in memory in a scattered way (locations). Each node's memory is allocated dynamically, that is, as and when it is needed. As a result, the linked list may grow as the user desires, and the size is not fixed; it can change.

How is the linked list different from the array?

An array is a grouping of items of the same data type. A linked list is an ordered collection of elements of the same type with pointers connecting each element to the next.

How do we check for palindromes in a linked list?

Traverse the linked list and save all of the linked list's elements in that string. Examine the linked list to see if the first and last characters are equivalent. This will not make a palindrome if they are not equal at some point.

Are linked lists (FIFO) or (LIFO)?

The LinkedList class implements the List, Deque, and Queue interfaces. The first-in, first-out (FIFO) principle governs how a queue stores and removes its components. LinkedList may be used to represent a first-in, first-out (FIFO) queue since it implements the Deque interface.

Why are linked lists used over arrays?

Linked lists are more efficient than arrays in terms of memory allocation. Unlike arrays, the size of a linked list is not fixed, so it can grow or shrink as the program runs.

Conclusion

In this article, we discussed the problem related to linked list and arbit and discussed its solution. We hope that this blog has helped you enhance your problem solving skill, and if you would like to learn more, check out our Linked List and Application of Linked List articles on Coding Ninjas Studio. Do upvote our blog to help other ninjas grow. Happy Coding!