Dada una lista enlazada , la tarea es encontrar el siguiente elemento mayor para cada Node de la lista enlazada.
Nota: Para los Nodes sin el siguiente elemento mayor, almacene -1 en el resultado.
Ejemplos:
Entrada: lista enlazada = [2, 1, 5]
Salida: [5, 5, -1]Entrada: lista enlazada = [2, 7, 4, 3, 5]
Salida: [7, -1, 5, 5, -1]
Enfoque:
para resolver el problema mencionado anteriormente, la idea principal es utilizar una estructura de datos de pila .
- Iterar a través de la lista vinculada e insertar el valor y la posición de los elementos de la lista vinculada en una pila.
- Inicialice el vector de resultados con -1 para cada Node.
- Actualice el valor del Node anterior mientras el valor del Node actual sea mayor que los Nodes anteriores y extraiga el valor de la pila después de la actualización.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to find the
// Next Greater Element for
// a Linked List
#include <bits/stdc++.h>
using namespace std;
// Linked List Node
struct Node {
int val;
struct Node* next;
};
// Function to print
// next greater element
vector<int> nextLargerNodes(
struct Node* head)
{
int cur_pos = 0;
stack<pair<int, int> > arr;
vector<int> res;
// Iterate for all
// element in linked list
while (head) {
// Initialize every
// position with 0
res.push_back(-1);
// Check if current value is
// greater then update previous
while (
!arr.empty()
&& arr.top().second
< head->val) {
res[arr.top().first]
= head->val;
arr.pop();
}
arr.push(make_pair(
cur_pos,
head->val));
cur_pos++;
// Increment the head pointer
head = head->next;
}
// Return the final result
return res;
}
// Utility function to
// create a new node
Node* newNode(int val)
{
struct Node* temp = new Node;
temp->val = val;
temp->next = NULL;
return temp;
}
// Driver Program
int main()
{
struct Node* head = newNode(2);
head->next = newNode(7);
head->next->next = newNode(4);
head->next->next->next = newNode(3);
head->next->next->next->next = newNode(5);
vector<int> ans;
ans = nextLargerNodes(head);
for (int i = 0; i < ans.size(); i++) {
cout << ans[i] << ", ";
}
}
Java
// Java Program to find the
// Next Greater Element for
// a Linked List
import java.util.*;
class GFG{
// Linked List Node
static class Node
{
int val;
Node next;
};
static class pair
{
int first, second;
public pair(int first,
int second)
{
this.first = first;
this.second = second;
}
} ;
// Function to print
// next greater element
static Vector<Integer>
nextLargerNodes(Node head)
{
int cur_pos = 0;
Stack<pair > arr = new Stack<>();
Vector<Integer> res = new Vector<>();
// Iterate for all
// element in linked list
while (head != null)
{
// Initialize every
// position with 0
res.add(-1);
// Check if current value is
// greater then update previous
while (!arr.isEmpty() &&
arr.peek().second <
head.val)
{
res.set(arr.peek().first,
head.val);
arr.pop();
}
arr.add(new pair(cur_pos,
head.val));
cur_pos++;
// Increment the head
// pointer
head = head.next;
}
// Return the final result
return res;
}
// Utility function to
// create a new node
static Node newNode(int val)
{
Node temp = new Node();
temp.val = val;
temp.next = null;
return temp;
}
// Driver code
public static void main(String[] args)
{
Node head = newNode(2);
head.next = newNode(7);
head.next.next = newNode(4);
head.next.next.next = newNode(3);
head.next.next.next.next = newNode(5);
Vector<Integer> ans = new Vector<>();
ans = nextLargerNodes(head);
for (int i = 0; i < ans.size(); i++)
{
System.out.print(ans.elementAt(i) + ", ");
}
}
}
// This code is contributed by Princi Singh
Python3
# Python3 program to find the # Next Greater Element for # a Linked List # Linked List Node class newNode: def __init__(self, val): self.val = val self.next = None # Function to print # next greater element def nextLargerNodes(head): cur_pos = 0 arr = [] res = [] # Iterate for all # element in linked list while (head): # Initialize every # position with 0 res.append(-1) # Check if current value is # greater then update previous while (len(arr) > 0 and arr[len(arr) - 1][1] < head.val): res[arr[len(arr) - 1][0]] = head.val arr.remove(arr[len(arr) - 1]) arr.append([cur_pos, head.val]) cur_pos += 1 # Increment the head pointer head = head.next # Return the final result return res # Driver code if __name__ == '__main__': head = newNode(2) head.next = newNode(7) head.next.next = newNode(4) head.next.next.next = newNode(3) head.next.next.next.next = newNode(5) ans = nextLargerNodes(head) for i in range(len(ans)): print(ans[i], end = ", ") # This code is contributed by SURENDRA_GANGWAR
C#
// C# Program to find the
// Next Greater Element for
// a Linked List
using System;
using System.Collections.Generic;
class GFG{
// Linked List Node
class Node
{
public int val;
public Node next;
};
class pair
{
public int first, second;
public pair(int first,
int second)
{
this.first = first;
this.second = second;
}
} ;
// Function to print
// next greater element
static List<int>
nextLargerNodes(Node head)
{
int cur_pos = 0;
Stack<pair > arr = new Stack<pair>();
List<int> res = new List<int>();
// Iterate for all
// element in linked list
while (head != null)
{
// Initialize every
// position with 0
res.Add(-1);
// Check if current value is
// greater then update previous
while (arr.Count !=0 &&
arr.Peek().second <
head.val)
{
res[arr.Peek().first] =
head.val;
arr.Pop();
}
arr.Push(new pair(cur_pos,
head.val));
cur_pos++;
// Increment the head
// pointer
head = head.next;
}
// Return the readonly result
return res;
}
// Utility function to
// create a new node
static Node newNode(int val)
{
Node temp = new Node();
temp.val = val;
temp.next = null;
return temp;
}
// Driver code
public static void Main(String[] args)
{
Node head = newNode(2);
head.next = newNode(7);
head.next.next = newNode(4);
head.next.next.next = newNode(3);
head.next.next.next.next = newNode(5);
List<int> ans = new List<int>();
ans = nextLargerNodes(head);
for (int i = 0; i < ans.Count; i++)
{
Console.Write(ans[i] + ", ");
}
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript program to find the
// Next Greater Element for
// a Linked List
// Linked List Node
class newNode{
constructor(val){
this.val = val
this.next = null
}
}
// Function to print
// next greater element
function nextLargerNodes(head){
let cur_pos = 0
let arr = []
let res = []
// Iterate for all
// element in linked list
while (head){
// Initialize every
// position with 0
res.push(-1)
// Check if current value is
// greater then update previous
while (arr.length> 0 && arr[arr.length- 1][1] < head.val){
res[arr[arr.length- 1][0]] = head.val
arr.pop()
}
arr.push([cur_pos, head.val])
cur_pos += 1
// Increment the head pointer
head = head.next
}
// Return the final result
return res
}
// Driver code
let head = new newNode(2)
head.next = new newNode(7)
head.next.next = new newNode(4)
head.next.next.next = new newNode(3)
head.next.next.next.next = new newNode(5)
ans = nextLargerNodes(head)
for(let i=0;i<ans.length;i++)
document.write(ans[i],", ")
// This code is contributed by shinjanpatra
</script>
Producción:
7, -1, 5, 5, -1,
Complejidad temporal: O(N)
Complejidad espacial auxiliar: O(N)