Dada una lista enlazada L de enteros, la tarea es devolver una lista enlazada de enteros que contenga el siguiente elemento mayor para cada elemento de la lista enlazada dada. Si no hay ningún elemento mayor para ningún elemento, inserte 0 para él.
Ejemplos:
Entrada: 2->1->3->0->5
Salida: 3->3->5->5->0Entrada: 1->2->3
Salida: 2->3->0
Enfoque ingenuo: el enfoque ingenuo es recorrer la lista vinculada L y, para cada elemento de la lista vinculada, encontrar el siguiente elemento mayor en la lista recorriendo toda la string desde el elemento actual. Como encontramos el siguiente elemento mayor para la cabeza actual, agregamos el siguiente elemento mayor a la array ans y, por último, devolvemos la array ans .
Java
// Java program for the above approach
import java.util.*;
public class linkedList {
ListNode head = null;
// ListNode
class ListNode {
int val;
ListNode next;
public ListNode(int val)
{
this.val = val;
next = null;
}
}
public int[] nextLargerLL(ListNode head)
{
// get size of LinkedList
int count = sizeOfLL(head);
// make size of ans array equal to size of LL i.e
// number of nodes in LL
int[] ans = new int[count];
// k is for index of ans array
int k = 0;
// j will be one step ahead of head node that will
// check the greater node
ListNode j;
// temp is for temporary storing the greater node
int temp = 0;
while (head != null) {
// if head.next is null it means there will be
// no greater node than head afterwards so add 0
// to ans array
if (head.next == null) {
ans[k] = 0;
break;
}
// j is one step ahead of head
j = head.next;
// if head.val is smaller than j.val so add
// j.val to ans array and increment index (k)
if (head.val < j.val) {
ans[k] = j.val;
k++;
}
else if (head.val
>= j.val) { // if head.val is greater
// than or equal to j.val
while (
j != null
&& head.val
>= j.val) { // search j.val such
// that it is greater
// than head.val
j = j.next;
}
/* if j is not equal to null it means we
* have got a value in LL which is greater
* than head so add j.val to ans array
* increment k after adding j.val
*/
if (j != null) {
ans[k] = j.val;
k++;
}
else { // it means we have not found any
// value which is greater than head so
// add 0 to ans array and increment
// index
ans[k] = 0;
k++;
}
}
else {
ans[k] = 0;
k++;
}
head = head.next;
}
return ans;
}
public void push(int new_data)
{
/* allocate node */
ListNode new_node = new ListNode(new_data);
/* link the old list off the new node */
new_node.next = head;
/* move the head to point to the new node */
head = new_node;
}
// Utility function to print the linked list
public void printList()
{
System.out.println(Arrays.toString(nextLargerLL(head)));
}
//driver code
public static void main(String[] args)
{
linkedList ll = new linkedList();
ll.push(5);
ll.push(0);
ll.push(3);
ll.push(1);
ll.push(2);
// Function Call
ll.nextLargerLL(ll.head);
ll.printList();
}
//to get size of LinkedList
public int sizeOfLL(ListNode head)
{
int count = 0;
while (head != null) {
count = count + 1;
head = head.next;
}
return count;
}
}
Python3
# Java program for the above approach head = None # ListNode class ListNode: def __init__(self, val): self.val = val self.next = None # to get size of LinkedList def sizeOfLL(head): count = 0 while (head != None): count = count + 1 head = head.next return count def nextLargerLL(head): # get size of LinkedList count = sizeOfLL(head) # make size of ans array equal to size of LL i.e # number of nodes in LL ans = [None]*count # k is for index of ans array k = 0 # j will be one step ahead of head node that will # check the greater node j = None # temp is for temporary storing the greater node temp = 0 while (head != None): # if head.next is None it means there will be # no greater node than head afterwards so add 0 # to ans array if (head.next == None): ans[k] = 0 break # j is one step ahead of head j = head.next # if head.val is smaller than j.val so add # j.val to ans array and increment index (k) if (head.val < j.val): ans[k] = j.val k += 1 elif (head.val >= j.val): # if head.val is greater # than or equal to j.val while ( j != None and head.val >= j.val): # search j.val such # that it is greater # than head.val j = j.next # if j is not equal to None it means we # have got a value in LL which is greater # than head so add j.val to ans array # increment k after adding j.val if (j != None): ans[k] = j.val k += 1 else: # it means we have not found any # value which is greater than head so # add 0 to ans array and increment # index ans[k] = 0 k += 1 else: ans[k] = 0 k += 1 head = head.next return ans def push(new_data): global head # allocate node None new_node = ListNode(new_data) # link the old list off the new node None new_node.next = head # move the head to point to the new node None head = new_node # Utility function to print the linked list def printList(): print(nextLargerLL(head)) # driver code if __name__ == '__main__': push(5) push(0) push(3) push(1) push(2) # Function Call nextLargerLL(head) printList()
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class linkedList {
ListNode head = null;
// ListNode
class ListNode {
public int val;
public ListNode next;
public ListNode(int val)
{
this.val = val;
next = null;
}
}
int[] nextLargerLL(ListNode head)
{
// get size of List
int count = sizeOfLL(head);
// make size of ans array equal to size of LL i.e
// number of nodes in LL
int[] ans = new int[count];
// k is for index of ans array
int k = 0;
// j will be one step ahead of head node that will
// check the greater node
ListNode j;
// temp is for temporary storing the greater node
int temp = 0;
while (head != null) {
// if head.next is null it means there will be
// no greater node than head afterwards so add 0
// to ans array
if (head.next == null) {
ans[k] = 0;
break;
}
// j is one step ahead of head
j = head.next;
// if head.val is smaller than j.val so add
// j.val to ans array and increment index (k)
if (head.val < j.val) {
ans[k] = j.val;
k++;
}
else if (head.val
>= j.val) { // if head.val is greater
// than or equal to j.val
while (
j != null
&& head.val
>= j.val) { // search j.val such
// that it is greater
// than head.val
j = j.next;
}
/* if j is not equal to null it means we
* have got a value in LL which is greater
* than head so add j.val to ans array
* increment k after adding j.val
*/
if (j != null) {
ans[k] = j.val;
k++;
}
else { // it means we have not found any
// value which is greater than head so
// add 0 to ans array and increment
// index
ans[k] = 0;
k++;
}
}
else {
ans[k] = 0;
k++;
}
head = head.next;
}
return ans;
}
public void push(int new_data)
{
/* allocate node */
ListNode new_node = new ListNode(new_data);
/* link the old list off the new node */
new_node.next = head;
/* move the head to point to the new node */
head = new_node;
}
// Utility function to print the linked list
void printList()
{
foreach(int a in nextLargerLL(head))
Console.Write(a+" ");
}
//driver code
public static void Main(String[] args)
{
linkedList ll = new linkedList();
ll.push(5);
ll.push(0);
ll.push(3);
ll.push(1);
ll.push(2);
// Function Call
ll.nextLargerLL(ll.head);
ll.printList();
}
//to get size of List
int sizeOfLL(ListNode head)
{
int count = 0;
while (head != null) {
count = count + 1;
head = head.next;
}
return count;
}
}
// This code is contributed by shikhasingrajput
Javascript
<script>
// JavaScript program for the above approach
let head = null
// ListNode
class ListNode
{
constructor(val)
{
this.val = val
this.next = null
}
}
// to get size of LinkedList
function sizeOfLL(head)
{
let count = 0
while (head != null)
{
count = count + 1
head = head.next
}
return count
}
function nextLargerLL(head)
{
// get size of LinkedList
let count = sizeOfLL(head)
// make size of ans array equal to size of LL i.e
// number of nodes in LL
let ans = new Array(count).fill(null)
// k is for index of ans array
let k = 0
// j will be one step ahead of head node that will
// check the greater node
let j = null
// temp is for temporary storing the greater node
let temp = 0
while (head != null)
{
// if head.next is null it means there will be
// no greater node than head afterwards so add 0
// to ans array
if (head.next == null){
ans[k] = 0
break
}
// j is one step ahead of head
j = head.next
// if head.val is smaller than j.val so add
// j.val to ans array and increment index (k)
if (head.val < j.val){
ans[k] = j.val
k += 1
}
else if (head.val >= j.val)
{
// if head.val is greater
// than or equal to j.val
while (j != null && head.val >= j.val)
{
// search j.val such
// that it is greater
// than head.val
j = j.next
}
// if j is not equal to null it means we
// have got a value in LL which is greater
// than head so add j.val to ans array
// increment k after adding j.val
if (j != null){
ans[k] = j.val
k += 1
}
else{
// it means we have not found any
// value which is greater than head so
// add 0 to ans array and increment
// index
ans[k] = 0
k += 1
}
}
else{
ans[k] = 0
k += 1
}
head = head.next
}
return ans
}
function push(new_data)
{
// allocate node null
let new_node = new ListNode(new_data)
// link the old list off the new node null
new_node.next = head
// move the head to point to the new node null
head = new_node
}
// Utility function to print the linked list
function printList(){
document.write(nextLargerLL(head))
}
// driver code
push(5)
push(0)
push(3)
push(1)
push(2)
// Function Call
nextLargerLL(head)
printList()
// This code is contributed by shinjanpatra
</script>
Producción
[3, 3, 5, 5, 0]
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar : O(1)
Enfoque eficiente: el enfoque ingenuo anterior se puede optimizar manteniendo una pila de elementos atravesados que disminuye monótonamente. Si se encuentra un elemento mayor, añádalo a la lista enlazada resultante . De lo contrario, añada 0 . A continuación se muestran los pasos:
- Empuje el primer Node para apilar.
- Elija el resto del Node uno por uno y siga los siguientes pasos en el bucle:
- Marque el Node actual como siguiente Node.
- Si la pila no está vacía, compare el valor del Node superior de la pila con el valor del siguiente Node.
- Si el valor del siguiente Node es mayor que el valor del Node superior, extraiga el Node superior de la pila y el siguiente es el siguiente elemento mayor para el Node extraído.
- Siga sacando el Node de la pila mientras el valor del Node sacado sea menor que el valor del siguiente Node. el siguiente Node se convertirá en el siguiente elemento mayor para todos esos Nodes reventados.
- Finalmente, empuje el siguiente Node en la pila.
- Después de que termine el bucle en el paso 2 , extraiga todos los Nodes de la pila e imprima 0 como el siguiente elemento para ellos.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// List Node
struct ListNode {
int val;
ListNode* next;
ListNode(int x)
{
val = x;
next = NULL;
}
};
// Function to reverse the LL
void rev(ListNode** head)
{
ListNode *pre, *curr, *nex;
pre = NULL;
curr = *head;
nex = curr->next;
// Till current is not NULL
while (curr) {
curr->next = pre;
pre = curr;
curr = nex;
nex = (curr)
? curr->next
: NULL;
}
*head = pre;
}
// Function to print a LL node
void printList(ListNode* head)
{
while (head) {
cout << head->val
<< ' ';
head = head->next;
}
}
// Function to find the next greater
// element in the list
ListNode* nextLargerLL(ListNode* head)
{
if (head == NULL)
return NULL;
// Dummy Node
ListNode* res
= new ListNode(-1);
ListNode* temp = res;
// Reverse the LL
rev(&head);
stack<int> st;
while (head) {
// Initial Condition
if (st.empty()) {
temp->next
= new ListNode(0);
st.push(head->val);
}
else {
// Maintain Monotonicity
// Decreasing stack of element
while (!st.empty()
&& st.top()
<= head->val)
st.pop();
// Update result LL
if (st.empty()) {
temp->next
= new ListNode(0);
st.push(head->val);
}
else {
temp->next
= new ListNode(st.top());
st.push(head->val);
}
}
head = head->next;
temp = temp->next;
}
// Delete Dummy Node
temp = res;
res = res->next;
delete temp;
// Reverse result LL
rev(&res);
return res;
}
// Driver Code
int main()
{
// Given Linked List
ListNode* head = new ListNode(2);
ListNode* curr = head;
curr->next = new ListNode(1);
curr = curr->next;
curr->next = new ListNode(3);
curr = curr->next;
curr->next = new ListNode(0);
curr = curr->next;
curr->next = new ListNode(5);
curr = curr->next;
// Function Call
printList(nextLargerLL(head));
return 0;
}
Java
// Java program for the above approach
import java.util.*;
public class linkedList
{
ListNode head = null;
// ListNode
class ListNode
{
int val;
ListNode next;
public ListNode(int val)
{
this.val = val;
next = null;
}
}
// Function to reverse the Linked List
ListNode reverse(ListNode head)
{
ListNode prev = null, next = null,
curr = head;
while (curr != null)
{
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
// Function to find the next greater
// element in the list
ListNode nextLargerLL(ListNode head)
{
if (head == null)
return head;
// Dummy Node
ListNode res = new ListNode(-1);
ListNode temp = res;
// Reverse the Linked List
head = reverse(head);
Stack<Integer> st = new Stack<>();
while (head != null)
{
// Initial Condition
if (st.empty())
{
temp.next = new ListNode(0);
st.push(head.val);
}
else {
// Maintain Monotonicity
// Decreasing stack of element
while (!st.empty() &&
st.peek() <= head.val)
st.pop();
// Update result Linked List
if (st.empty())
{
temp.next = new ListNode(0);
st.push(head.val);
}
else
{
temp.next = new ListNode(st.peek());
st.push(head.val);
}
}
head = head.next;
temp = temp.next;
}
temp = res;
res = res.next;
// Reverse result Linked List
res = reverse(res);
return res;
}
public void push(int new_data)
{
/* allocate node */
ListNode new_node = new ListNode(new_data);
/* link the old list off the new node */
new_node.next = head;
/* move the head to point to the new node */
head = new_node;
}
// Utility function to print the linked list
public void printList(ListNode head)
{
ListNode temp = head;
while (temp != null)
{
System.out.print(temp.val + " ");
temp = temp.next;
}
}
// Driver Code
public static void main(String[] args)
{
linkedList ll = new linkedList();
ll.push(5);
ll.push(0);
ll.push(3);
ll.push(1);
ll.push(2);
// Function Call
ll.printList(ll.nextLargerLL(ll.head));
}
}
Python3
# Python3 program for the above approach # List Node class ListNode: def __init__(self, x): self.val = x self.next = None # Function to reverse the LL def rev(head): pre = None; curr = head; nex = curr.next; # Till current is not None while (curr): curr.next = pre; pre = curr; curr = nex; nex = (curr.next) if curr else None head = pre return head # Function to print a LL node def printList(head): while(head): print(str(head.val), end = ' ') head = head.next; # Function to find the next greater # element in the list def nextLargerLL(head): if (head == None): return None; # Dummy Node res = ListNode(-1); temp = res; # Reverse the LL head = rev(head); st = [] while (head): # Initial Condition if (len(st) == 0): temp.next = ListNode(0); st.append(head.val); else: # Maintain Monotonicity # Decreasing stack of element while (len(st) != 0 and st[-1]<= head.val): st.pop(); # Update result LL if (len(st) == 0): temp.next = ListNode(0); st.append(head.val); else: temp.next = ListNode(st[-1]); st.append(head.val); head = head.next; temp = temp.next; # Delete Dummy Node temp = res; res = res.next; del temp; # Reverse result LL res = rev(res); return res; # Driver Code if __name__=='__main__': # Given Linked List head = ListNode(2); curr = head; curr.next = ListNode(1); curr = curr.next; curr.next = ListNode(3); curr = curr.next; curr.next = ListNode(0); curr = curr.next; curr.next = ListNode(5); curr = curr.next; # Function Call printList(nextLargerLL(head)); # This code is contributed by rutvik_56
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class linkedList{
ListNode head = null;
// ListNode
public class ListNode
{
public int val;
public ListNode next;
public ListNode(int val)
{
this.val = val;
next = null;
}
}
// Function to reverse the Linked List
ListNode reverse(ListNode head)
{
ListNode prev = null, next = null,
curr = head;
while (curr != null)
{
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
// Function to find the next greater
// element in the list
ListNode nextLargerLL(ListNode head)
{
if (head == null)
return head;
// Dummy Node
ListNode res = new ListNode(-1);
ListNode temp = res;
// Reverse the Linked List
head = reverse(head);
Stack<int> st = new Stack<int>();
while (head != null)
{
// Initial Condition
if (st.Count == 0)
{
temp.next = new ListNode(0);
st.Push(head.val);
}
else
{
// Maintain Monotonicity
// Decreasing stack of element
while (st.Count != 0 &&
st.Peek() <= head.val)
st.Pop();
// Update result Linked List
if (st.Count == 0)
{
temp.next = new ListNode(0);
st.Push(head.val);
}
else
{
temp.next = new ListNode(st.Peek());
st.Push(head.val);
}
}
head = head.next;
temp = temp.next;
}
temp = res;
res = res.next;
// Reverse result Linked List
res = reverse(res);
return res;
}
public void Push(int new_data)
{
// Allocate node
ListNode new_node = new ListNode(new_data);
// Link the old list off the new node
new_node.next = head;
// Move the head to point to the new node
head = new_node;
}
// Utility function to print the linked list
public void printList(ListNode head)
{
ListNode temp = head;
while (temp != null)
{
Console.Write(temp.val + " ");
temp = temp.next;
}
}
// Driver Code
public static void Main(String[] args)
{
linkedList ll = new linkedList();
ll.Push(5);
ll.Push(0);
ll.Push(3);
ll.Push(1);
ll.Push(2);
// Function Call
ll.printList(ll.nextLargerLL(ll.head));
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// Javascript program for the above approach
// List Node
class ListNode {
constructor(x)
{
this.val = x;
this.next = null;
}
};
// Function to reverse the LL
function rev(head)
{
var pre, curr, nex;
pre = null;
curr = head;
nex = curr.next;
// Till current is not null
while (curr) {
curr.next = pre;
pre = curr;
curr = nex;
nex = (curr)
? curr.next
: null;
}
head = pre;
return head;
}
// Function to print a LL node
function printList( head)
{
while (head) {
document.write( head.val
+ ' ');
head = head.next;
}
}
// Function to find the next greater
// element in the list
function nextLargerLL(head)
{
if (head == null)
return null;
// Dummy Node
var res
= new ListNode(-1);
var temp = res;
// Reverse the LL
head = rev(head);
var st = [];
while (head) {
// Initial Condition
if (st.length==0) {
temp.next
= new ListNode(0);
st.push(head.val);
}
else {
// Maintain Monotonicity
// Decreasing stack of element
while (st.length != 0
&& st[st.length - 1]
<= head.val)
st.pop();
// Update result LL
if (st.length == 0) {
temp.next
= new ListNode(0);
st.push(head.val);
}
else {
temp.next
= new ListNode(st[st.length - 1]);
st.push(head.val);
}
}
head = head.next;
temp = temp.next;
}
// Delete Dummy Node
temp = res;
res = res.next;
delete temp;
// Reverse result LL
res = rev(res);
return res;
}
// Driver Code
// Given Linked List
var head = new ListNode(2);
var curr = head;
curr.next = new ListNode(1);
curr = curr.next;
curr.next = new ListNode(3);
curr = curr.next;
curr.next = new ListNode(0);
curr = curr.next;
curr.next = new ListNode(5);
curr = curr.next;
// Function Call
printList(nextLargerLL(head));
// This code is contributed by noob2000.
</script>
Producción
3 3 5 5 0
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por AnshulVerma1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA