Leveraging ChatGPT - GenAI as a Microsoft Data Expert

Speaker

Prerita Agarwal

Data Specialist @

23 Jul, 2024 @ 01:30 PM

Introduction

A linked list is a sequential data that contains nodes and their addresses linked to the previous node. The first node in the linked list is the "head" node, and the address field of the last node is pointed to null. There are three types of linked lists. They are

In this article, let’s learn how to point a node to its next higher value node in a linked list.

Linked List implementation

We have to connect every node to its higher node in a linked list. So to connect these nodes we must find the node with the higher value. If a linked list has two or more fields, the second pointer in it is called the arbitrary pointer, which initially points to null, and we can update it to point to any node. Each node in the singly linked list has an “arbitrary” pointer that points to null. The arbitrary pointer is used to point to the next node having a greater value. Suppose we have a linked list with a few values as shown below.

Let’s consider an initial linked list consisting of elements such as 5,8,2,4.

By using the Brute Force technique we compare each element with all the leftover elements in the linked list and update the current node pointer to the next node having a greater value. 5 is compared to 8, 2, 4 and the current node is pointed to the greater element. In the above case, the arbitrary pointer is pointed to 8. The same process as above is followed for the rest of the elements in the linked list.

In the above scenario, after using the brute force technique for the linked list, we can see that 2 points to 4, 4 to 5, and 5 to 8. In this way, the final linked list consists of nodes connected sequentially. The time complexity for solving the above problem using the Brute Force technique is O(n^2).

The most efficient way for solving this problem is by using the merge sort concept for sorting the elements and connecting them to the next nodes in the linked list. We prefer the merge sort technique as its time complexity for solving this problem is O(NlogN) which is more efficient than the brute force technique.

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Merge sort implementation

We can implement the merge sort on the linked list as mentioned below.

Initially, we traverse the input linked list and update the next pointer to the arbitrary pointer for every node.

Then we perform the merge sort on the linked list obtained as a result of the connection of the next pointer to an arbitrary pointer.

In this article, let’s learn how to solve this problem using merge sort.

#include <iostream>
using namespace std;
class Node {
public:
int num;
Node* next, *arbitrary;
};
//this method sorts the list in an order
Node* Sort(Node* a, Node* b);
//this method splits the linked list into two parts
void SplitNode(Node* source, Node** frontRef, Node** backRef);
Node* Sort(Node* a, Node* b) {
Node* result = NULL;
if (a == NULL)
return (b);
else if (b == NULL)
return (a);
if (a->num <= b->num){
result = a;
result->arbitrary = Sort(a->arbitrary, b);
} else {
result = b;
result->arbitrary = Sort(a, b->arbitrary);
}
return (result);
}
void SplitNode(Node* source, Node** frontRef, Node** backRef) {
Node* fast, *slow;
if (source == NULL || source->arbitrary == NULL){
*frontRef = source;
*backRef = NULL;
return;
}
slow = source, fast = source->arbitrary;
while (fast != NULL){
fast = fast->arbitrary;
if (fast != NULL){
slow = slow->arbitrary;
fast = fast->arbitrary;
}
}
*frontRef = source;
*backRef = slow->arbitrary;
slow->arbitrary = NULL;
}
//this method merges the linked list after the split
void Merge(Node** headRef) {
Node* head = *headRef;
Node* a, *b;
if ((head == NULL) || (head->arbitrary == NULL))
return;
SplitNode(head, &a, &b);
Merge(&a);
Merge(&b);
*headRef = Sort(a, b);
}
void addNode(Node** head_ref, int new_data) {
Node* new_node = new Node();
new_node->num = new_data;
new_node->next = (*head_ref);
new_node->arbitrary = NULL;
(*head_ref) = new_node;
}
Node* connectArbitrary(Node *head) {
Node *temp = head;
while (temp != NULL){
temp->arbitrary = temp->next;
temp = temp->next;
}
Merge(&head);
return head;
}
int main() {
Node* head = NULL;
addNode(&head, 5);
addNode(&head, 8);
addNode(&head, 2);
addNode(&head, 4);
Node *front = connectArbitrary(head);
cout << "Traversing linked List\n";
cout<<"Using Next Pointer\n";
while (head!=NULL){
cout << head->num << ", ";
head = head->next;
}
printf("\nUsing Arbitrary Pointer\n");
while (front!=NULL){
cout<<front->num<<", ";
front = front->arbitrary;
}
return 0;
}

Output

Traversing linked List

Using Next Pointer

4, 2, 8, 5

Using Arbitrary Pointer

2, 4, 5, 8

The above program sort() function is created to sort the linked list by changing the next pointer. The linked list is split into a and b sublists using SplitNode() function and is recursively sorted. The sorted lists are merged using the merge() function. The solution obtained using the merge sort technique has a time complexity of O(NlogN).

FAQs

What is a linked list?

A linked list is a sequential data that contains nodes and their addresses linked to the previous node. The first node in the linked list is called the head node, and the address field of the last node is pointed to null.

What are the types of linked lists?

There are three types of linked lists in data structures. They are; Single linked lists, Circular linked lists and Doubly linked lists.

What is the purpose of the next or link pointer in the node?

The next pointer or the link pointer in a linked list stores the address of the data field of the next node, which stores the element or data.

Which is the best method to point a node to the next higher value?

The merge sort technique is the best method that can be used to point a node to its high-value node in a linked list. This method traverses the linked list, sorts them, and then points the node to the higher value and merges them.

What is an arbitrary pointer in a linked list?

If a linked list has two or more fields, the second pointer in it is called the arbitrary pointer, which initially points to null, and we can update it to point to any node.

Key Takeaways

We have discussed the concept of the linked list and how to point a node to its higher value in a linked list in this article.

Hey Ninjas! We hope this blog helped you better to understand the linked list concept. Please check out Coding Ninjas for more unique courses and guided paths. Also, try Coding Ninjas Studio for more exciting articles, interview experiences, and fantastic Data Structures and Algorithms problems. Please upvote our blog to help the other ninjas grow.