Find the Previous Closest Smaller Node in a Singly Linked List
Given a singly linked list, the task is to find the previous closest smaller node for every node in a linked list.
Examples:
Input: 5 -> 6 -> 8 -> 2 -> 3 -> 4
Output: -1 -> 5 -> 6 -> -1 -> 2 -> 3
Explanation:
- For the first node 5, there is no previous closest smaller node so it is replaced with -1.
- For the second node 6, the previous closest smaller node is 5, so it is replaced with 5.
- For the third node 8, the previous closest smaller node is 6, so it is replaced with 6.
- For the fourth node 2, there is no previous closest smaller node so it is replaced with -1.
- For the fifth node 3, the previous closest smaller node is 2, so it is replaced with 2.
- For the sixth node 4, the previous closest smaller node is 3, so it is replaced with 3.
Input: 9 -> 2 -> 7 -> 4 -> 6
Output: -1 -> -1 -> 2 -> 2 -> 4
Explanation:
- For the first node 9, there is no previous closest smaller node so it is replaced with -1.
- For the second node 2, there is no previous closest smaller node so it is replaced with -1.
- For the third node 7, the previous closest smaller node is 2, so it is replaced with 2.
- For the fourth node 4, the previous closest smaller node is 2, so it is replaced with 2.
- For the fifth node 6, the previous closest smaller node is 4, so it is replaced with 4.
Approach: To solve the problem follow the below idea:
The intuition behind this approach is to use a stack to keep track of the previous smaller elements as we traverse the linked list. For each node in the linked list, we pop elements from the stack that are greater than or equal to the current node’s value until we find an element smaller than the current node’s value. The top element of the stack at this point is the previous smaller element for the current node. We then push the current node’s value onto the stack and create a new node in a separate linked list with the value of the previous smaller element. We continue this process for all nodes in the original linked list, and the resulting linked list contains the previous smaller element for each node.
Steps of this approach:
- Create an empty stack to store the nodes of the list.
- Traverse the list, starting from the head node.
- For each node, pop all nodes from the stack that have values greater than or equal to the current node’s value, until either the stack is empty or the top node’s value is less than the current node’s value.
- If the stack is not empty, then the previous smaller node for the current node is the top node of the stack. Otherwise, there is no previous smaller node, and we can set it to -1.
- Push the current node onto the stack.
- Repeat steps 3-5 until the end of the list is reached.
- Create a new linked list using the values of the previous smaller nodes we found, and return it as the result.
Implementation of the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Structure for a linked list node struct Node { int data; Node* next; }; // Function to create a new node // with the given data Node* createNode( int data) { Node* node = new Node; node->data = data; node->next = NULL; return node; } // Function to find the previous closest // smaller element for each node Node* findPrevSmaller(Node* head) { // Create a stack to track elements stack< int > s; // Pointer to traverse the input linked list Node* curr = head; // Variable to store the previous // closest smaller element int prevSmaller; // Resulting linked list to store previous // closest smaller elements Node* result = NULL; while (curr != NULL) { // Initialize prevSmaller to -1 // for the first element prevSmaller = -1; // Pop elements from the stack until // a smaller element is found or // the stack is empty while (!s.empty() && s.top() >= curr->data) { s.pop(); } if (!s.empty()) { // The top element of the stack // is the previous closest // smaller element prevSmaller = s.top(); } // Push the current element onto // the stack s.push(curr->data); // Create a new node with the // previous closest smaller // element Node* newNode = createNode(prevSmaller); // If the result list is empty, // set it to the new node if (result == NULL) { result = newNode; } else { Node* temp = result; // Find the end of the result list // and add the new node while (temp->next != NULL) { temp = temp->next; } temp->next = newNode; } // Move to the next node in the // input linked list curr = curr->next; } return result; } // Function to print the elements // in a linked list void printList(Node* head) { while (head != NULL) { if (head->next != NULL) { cout << head->data << " -> "; } else { cout << head->data << "\n"; } head = head->next; } } // Drivers code int main() { // Create the input linked list: // 5 -> 6 -> 8 -> 2 -> 3 -> 4 Node* head = createNode(5); head->next = createNode(6); head->next->next = createNode(8); head->next->next->next = createNode(2); head->next->next->next->next = createNode(3); head->next->next->next->next->next = createNode(4); // Find the list of previous closest // smaller elements for each node Node* result = findPrevSmaller(head); // Display the result cout << "List with Previous Closest Smaller Nodes: "; printList(result); return 0; } |
Java
import java.util.Stack; // Structure for a linked list node class Node { int data; Node next; // Constructor to create a new node with the given data Node( int data) { this .data = data; this .next = null ; } } public class PrevClosestSmaller { // Function to find the previous closest smaller element for each node static Node findPrevSmaller(Node head) { // Create a stack to track elements Stack<Integer> s = new Stack<>(); // Pointer to traverse the input linked list Node curr = head; // Variable to store the previous closest smaller element int prevSmaller; // Resulting linked list to store previous closest smaller elements Node result = null ; while (curr != null ) { // Initialize prevSmaller to -1 for the first element prevSmaller = - 1 ; // Pop elements from the stack until a smaller element is found or the stack is empty while (!s.isEmpty() && s.peek() >= curr.data) { s.pop(); } if (!s.isEmpty()) { // The top element of the stack is the previous closest smaller element prevSmaller = s.peek(); } // Push the current element onto the stack s.push(curr.data); // Create a new node with the previous closest smaller element Node newNode = new Node(prevSmaller); // If the result list is empty, set it to the new node if (result == null ) { result = newNode; } else { Node temp = result; // Find the end of the result list and add the new node while (temp.next != null ) { temp = temp.next; } temp.next = newNode; } // Move to the next node in the input linked list curr = curr.next; } return result; } // Function to print the elements in a linked list static void printList(Node head) { while (head != null ) { if (head.next != null ) { System.out.print(head.data + " -> " ); } else { System.out.println(head.data); } head = head.next; } } // Driver's code public static void main(String[] args) { // Create the input linked list: 5 -> 6 -> 8 -> 2 -> 3 -> 4 Node head = new Node( 5 ); head.next = new Node( 6 ); head.next.next = new Node( 8 ); head.next.next.next = new Node( 2 ); head.next.next.next.next = new Node( 3 ); head.next.next.next.next.next = new Node( 4 ); // Find the list of previous closest smaller elements for each node Node result = findPrevSmaller(head); // Display the result System.out.print( "List with Previous Closest Smaller Nodes: " ); printList(result); } } |
Python3
# Structure for a linked list node class Node: def __init__( self , data): self .data = data self . next = None # Function to find the previous closest smaller element for each node def find_prev_smaller(head): # Create a stack to track elements stack = [] # Pointer to traverse the input linked list curr = head # Variable to store the previous closest smaller element prev_smaller = None # Resulting linked list to store previous closest smaller elements result = None while curr: # Initialize prevSmaller to None for the first element prev_smaller = None # Pop elements from the stack until a smaller element is found or the stack is empty while stack and stack[ - 1 ] > = curr.data: stack.pop() if stack: # The top element of the stack is the previous closest smaller element prev_smaller = stack[ - 1 ] # Push the current element onto the stack stack.append(curr.data) # Create a new node with the previous closest smaller element new_node = Node(prev_smaller) # If the result list is empty, set it to the new node if not result: result = new_node else : temp = result # Find the end of the result list and add the new node while temp. next : temp = temp. next temp. next = new_node # Move to the next node in the input linked list curr = curr. next return result # Function to print the elements in a linked list def print_list(head): while head: if head. next : print (head.data if head.data is not None else - 1 , end = " -> " ) else : print (head.data if head.data is not None else - 1 ) head = head. next # Driver code if __name__ = = "__main__" : # Create the input linked list: 5 -> 6 -> 8 -> 2 -> 3 -> 4 head = Node( 5 ) head. next = Node( 6 ) head. next . next = Node( 8 ) head. next . next . next = Node( 2 ) head. next . next . next . next = Node( 3 ) head. next . next . next . next . next = Node( 4 ) # Find the list of previous closest smaller elements for each node result = find_prev_smaller(head) # Display the result print ( "List with Previous Closest Smaller Nodes:" , end = " " ) print_list(result) # This code is contributed by shivamgupta0987654321 |
C#
using System; using System.Collections.Generic; // Structure for a linked list node public class Node { public int data; public Node next; } class Program { // Function to create a new node with the given data static Node CreateNode( int data) { Node node = new Node(); node.data = data; node.next = null ; return node; } // Function to find the previous closest smaller element for each node static Node FindPrevSmaller(Node head) { // Create a stack to track elements Stack< int > stack = new Stack< int >(); // Pointer to traverse the input linked list Node curr = head; // Variable to store the previous closest smaller element int prevSmaller; // Resulting linked list to store previous closest smaller elements Node result = null ; while (curr != null ) { // Initialize prevSmaller to -1 for the first element prevSmaller = -1; // Pop elements from the stack until a smaller element is found or the stack is empty while (stack.Count > 0 && stack.Peek() >= curr.data) { stack.Pop(); } if (stack.Count > 0) { // The top element of the stack is the previous closest smaller element prevSmaller = stack.Peek(); } // Push the current element onto the stack stack.Push(curr.data); // Create a new node with the previous closest smaller element Node newNode = CreateNode(prevSmaller); // If the result list is empty, set it to the new node if (result == null ) { result = newNode; } else { Node temp = result; // Find the end of the result list and add the new node while (temp.next != null ) { temp = temp.next; } temp.next = newNode; } // Move to the next node in the input linked list curr = curr.next; } return result; } // Function to print the elements in a linked list static void PrintList(Node head) { while (head != null ) { if (head.next != null ) { Console.Write(head.data + " -> " ); } else { Console.WriteLine(head.data); } head = head.next; } } // Drivers code static void Main() { // Create the input linked list: 5 -> 6 -> 8 -> 2 -> 3 -> 4 Node head = CreateNode(5); head.next = CreateNode(6); head.next.next = CreateNode(8); head.next.next.next = CreateNode(2); head.next.next.next.next = CreateNode(3); head.next.next.next.next.next = CreateNode(4); // Find the list of previous closest smaller elements for each node Node result = FindPrevSmaller(head); // Display the result Console.Write( "List with Previous Closest Smaller Nodes: " ); PrintList(result); } } |
Javascript
// Structure for a linked list node class Node { constructor(data) { this .data = data; this .next = null ; } } // Function to find the previous closest smaller element for each node function findPrevSmaller(head) { // Create a stack to track elements const stack = []; let curr = head; let prevSmaller; let result = null ; while (curr !== null ) { prevSmaller = -1; // Pop elements from the stack until a smaller element is found or the stack is empty while (stack.length > 0 && stack[stack.length - 1] >= curr.data) { stack.pop(); } if (stack.length > 0) { // The top element of the stack is the previous closest smaller element prevSmaller = stack[stack.length - 1]; } // Push the current element onto the stack stack.push(curr.data); // Create a new node with the previous closest smaller element const newNode = new Node(prevSmaller); if (result === null ) { result = newNode; } else { let temp = result; // Find the end of the result list and add the new node while (temp.next !== null ) { temp = temp.next; } temp.next = newNode; } // Move to the next node in the input linked list curr = curr.next; } return result; } // Function to print the elements in a linked list function printList(head) { let current = head; let listString = "List with Previous Closest Smaller Nodes: " ; while (current !== null ) { if (current.next !== null ) { listString += current.data + " -> " ; } else { listString += current.data; } current = current.next; } console.log(listString); } // Driver's code // Create the input linked list: 5 -> 6 -> 8 -> 2 -> 3 -> 4 const head = new Node(5); head.next = new Node(6); head.next.next = new Node(8); head.next.next.next = new Node(2); head.next.next.next.next = new Node(3); head.next.next.next.next.next = new Node(4); // Find the list of previous closest smaller elements for each node const result = findPrevSmaller(head); // Display the result printList(result); |
List with Previous Closest Smaller Nodes: -1 -> 5 -> 6 -> -1 -> 2 -> 3
Time Complexity: O(n), where n is the number of nodes in the linked list.
Auxiliary Space: O(n), where n is the number of nodes in the linked list. This is because we use a stack to store the previous smaller elements and a linked list to store the result.