A linked list is a data structure that stores the data(information) in a node. Every node in a linked list stores the address to its neighboring node.
The last node of the linked list points to a NULL address representing the end of the linked list. To traverse the linked list, the address to the first node is stored in a node usually called ‘HEAD’.
A node with a value strictly greater than its adjacent nodes is usually called a local maxima.
Similarly, a node with a value strictly smaller than its adjacent nodes is usually called a local minimum.
Both local maxima and local minima are types of critical points. So, a critical point in the linked list is one where the node of a linked list is either strictly greater or smaller than both of its adjacent nodes.
The first and last nodes of the linked list have only one adjacent node. So, they can’t be considered as critical points.
Problem statement
The ‘HEAD’ pointer of a linked list is given. Find the minimum and maximum distance between two critical points of the linked list. If no such answer exists, return -1 as the minimum and maximum distance.
Input
Enter the number of nodes in the linked list: 7
Enter the data of nodes: 5 3 1 2 5 1
Output
The minimum distance between two critical points is 1
The maximum distance between two critical points is 3
Explanation
Critical points are at positions 2, 4, and 5.
The minimum distance is the distance between the subsequent critical points. Here, the closest critical positions are 4 and 5. So, the minimum distance is 1.
Maximum distance is the distance between the first and last critical points of the linked list. So, the maximum distance is 5 - 2 = 3
Approach
Consider a node pointer ‘CURRENT’ used to traverse through the linked list. The ‘CURRENT’ node pointer describes the node at present during traversal. To check whether the given node is local minima or local maxima, we need to compare the current node's value with the previous node and the next node. For this purpose, we use two pointers: ‘PREVIOUS_TO_CURRENT’ and ‘NEXT_TO_CURRENT’ for the same.
It is well understood that the maximum distance possible for two critical points is when the critical nodes are first and last.
The minimum distance possible between two critical points is the distance between two subsequent critical points. Refer to the figure given above for a better understanding.
Traverse through the linked list to find the first critical point. Store the position of the first critical point to calculate the maximum distance. Also, while traversing the linked list, store the position of the previously encountered linked list to calculate the minimum distance. Refer to the algorithm given below for a better understanding.
Algorithm
Set ‘MIN_DISTANCE’ to the maximum value possible(INT_MAX).
Set ‘MAX_DISTANCE’ to the least value(-1).
If ‘HEAD’ points to NULL(means list is empty), then:
Return -1 as minimum and maximum distance.
Initialize the ‘PREVIOUS_TO_CURRENT’ pointer as ’HEAD’.
Initialize the ‘CURRENT’ pointer as PREVIOUS_TO_CURRENT -> NEXT.
Set PREVIOUS_INDEX = -1, CURRENT_INDEX = 1, and FIRST_INDEX = -1.
While CURRENT -> NEXT is not NULL, do:
Initialize ‘NEXT_TO_CURRENT’ with CURRENT -> NEXT.
If CURRENT satisfies the conditions of local minima or local maxima, then:
If PREVIOUS_INDEX = -1(means no first index is found), then:
Set PREVIOUS_INDEX = CURRENT_INDEX.
Set FIRST_INDEX = CURRENT_INDEX.
Else:
Set MIN_DISTANCE = min(MIN_DISTANCE, CURRENT_INDEX - PREVIOUS_INDEX).
Set MAX_DISTANCE = max(MAX_DISTANCE, CURRENT_INDEX - FIRST_INDEX).
Move CURRENT and ‘PREVIOUS_TO_CURRENT’ pointer ahead.
Set PREVIOUS_TO_CURRENT = CURRENT.
Set CURRENT = NEXT_TO_CURRENT.
Increment CURRENT_INDEX .
If ‘MAX_DISTANCE’ is -1 (means no pair of critical point is found), then:
Return -1 as minimum and maximum distance.
Else:
Return ‘MIN_DISTANCE’ and ‘MAX_DISTANCE’.
Program
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
// 'NODE' class to store linked list nodes.
class Node
{
public:
int data;
Node *next;
// Constructor to create a node with given data.
Node(int data)
{
this->data = data;
next = NULL;
}
};
// 'LINKED_LIST' class to create linked list objects.
class LinkedList
{
// 'HEAD' node to store the address of the first node.
Node *head;
public:
LinkedList()
{
head = NULL;
}
// Function to print the linked list elements.
void printLinkedList()
{
/* 'CURRENT' node pointer traverses through the linked list.
Set 'CURRENT' node equal to first node of the linked list.
*/
Node *current = head;
// Loop to traverse the linked list.
while (current)
{
cout << current->data << " ";
current = current->next;
}
cout << endl;
}
// Function to insert nodes in the linked list.
void insert(int data)
{
/* If linked list is empty, create a new node
and direct the 'HEAD' node to the newly created node.
*/
if (head == NULL)
{
head = new Node(data);
return;
}
// Else traverse the linked list until end of the list is encountered.
Node *current = head;
while (current->next)
{
current = current->next;
}
// Create and insert a new node at the end of the linked list.
current->next = new Node(data);
}
vector<int> nodesBetweenCriticalPoints()
{
int minDistance = INT_MAX, maxDistance = -1;
// If ‘HEAD’ points to NULL(means list is empty).
if (!head && !head->next)
return {-1, -1};
// 'PREVIOUS_INDEX', 'CURRENT_INDEX', and 'FIRST_INDEX' to store node positions.
int previousIndex = -1, currentIndex = 1, firstIndex = -1;
// Initialize node pointers to traverse the linked list.
Node *previoustocurrent = head;
Node *current = previoustocurrent->next;
// While the 'CURRENT' node does not reach to the last node.
while (current->next && currentIndex++)
{
Node *nextToCurrent = current->next;
// If CURRENT satisfies the conditions of local minima or local maxima.
if ((current->data > previoustocurrent->data && current->data > nextToCurrent->data) || (current->data < previoustocurrent->data && current->data < nextToCurrent->data))
// If PREVIOUS_INDEX = -1(means no first index is found).
if (previousIndex == -1)
{
previousIndex = currentIndex;
firstIndex = currentIndex;
}
else
{
minDistance = min(minDistance, currentIndex - previousIndex);
maxDistance = max(maxDistance, currentIndex - firstIndex);
previousIndex = currentIndex;
}
// Move CURRENT and 'PREVIOUS_TO_CURRENT' pointer ahead.
previoustocurrent = current;
current = current->next;
}
if (maxDistance == -1)
return {-1, -1};
return {minDistance, maxDistance};
}
};
int main()
{
int totalNodes;
cout << "Enter the number of nodes in the linked list: ";
cin >> totalNodes;
cout << "Enter the data of nodes:\n";
LinkedList *givenList = new LinkedList();
for (int i = 0; i < totalNodes; i++)
{
int data;
cin >> data;
givenList->insert(data);
}
// 'ANSWER' vector to store the output of the function.
vector<int> answer = givenList->nodesBetweenCriticalPoints();
cout << "The minimum distance between two critical points is " << answer[0];
cout << "\nThe maximum distance between two critical points is " << answer[1];
}
You can also try this code with Online C++ Compiler
Enter the number of nodes in the linked list: 7
Enter the data of nodes: 5 3 1 2 5 1 2
Output
The minimum distance between two critical points is 1
The maximum distance between two critical points is 3
Complexity Analysis
Time complexity: The code requires traversal through the linked list. The linked list traversal is a linear-time operation. So, the time complexity of this method is O(N), where ‘N’ represents the number of nodes present in the linked list.
Space complexity: Constant space is required to store variables for the computation of ‘MIN_DISTANCE’ and ‘MAX_DISTANCE’. The space complexity of the code is O(1).
What is the time complexity for searching an element in a Linked List?
Since to access an element in a Linked List, the Node consisting of a pointer to it also has to be accessed so the searching occurs in O(N) time where N is the number of nodes.
Can we access the nodes of a Linked List by using indexing as in an array?
No, to access a node of a linked list it is necessary to have an address pointer to its previous node making accessing the linked list node possible in a chain like fashion.
Conclusion
Sometimes the problem statement may sound complicated. There may be many terms we might be hearing for the first time. We should not just quit right away. If you require, read the problem statement again and again. With every read, you might get to know what may sound like a complex problem is just a variation of a simpler problem - saying that, congratulations on your learning.
At Coding Ninjas Studio, we try our best to make your learning experience easy, interesting, and efficient. Refer to our library for more such interesting blogs.
46+ registered 