Dada una lista enlazada lis de longitud N , la tarea es determinar la distancia máxima entre dos picos consecutivos de la lista enlazada dada. Un pico se define como un Node que tiene un valor mayor que sus vecinos. La distancia entre dos Nodes se define como el número de Nodes presentes entre ellos.
Ejemplos:
Entrada : lis = 1 -> 2 -> 3 -> 1 -> 5 -> 4 -> 4 -> 10 -> 7 Salida: 2
Explicación :
Los picos en la lista enlazada son 3, 5, 10
La distancia entre 3 y 5 es 1.
La distancia entre 5 y 10 es 2.
La distancia máxima es 2.Entrada : lis = 1 -> 3 -> 1 -> 1 ->1 -> 1 -> 4 -> 2 -> 7 Salida: 4
Explicación :
Los picos en la lista enlazada son 3, 4, 7
La distancia entre 3 y 4 es 4.
La distancia entre 4 y 7 es 1.
La distancia máxima es 4.
Enfoque: La solución se basa en el enfoque codicioso . Siga los pasos que se mencionan a continuación para resolver el problema:
- Iterar sobre la lista enlazada y encontrar Nodes que sean picos .
- Mantenga un registro del índice anterior que es el pico y el índice actual si es un pico
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to implement the above approach
#include <bits/stdc++.h>
using namespace std;
// Class(struct) for the structure of a node
struct Node {
int data;
Node* next;
Node(int data, Node* next)
: data(data)
, next(next)
{
}
};
// Function to find the maximum distance
void findMaxGap(Node* head)
{
// Pre points to previous of current node
Node* pre = new Node(-1, head);
// Current is initially head
Node* cur = head;
int lastIndex = -1, currentIndex = 0, maxGap = 0,
gap = 0;
// Loop till current is not NULL
while (cur != NULL) {
// Find next of current
Node* next = cur->next;
// One node only
if (pre->next == head && next == NULL) {
cout << maxGap;
return;
}
// For the 1st node check only next
else if (pre->next == head
&& next->data < cur->data) {
lastIndex = currentIndex;
}
// For the last node check
// only the prev node
else if (next == NULL && pre->data < cur->data) {
if (lastIndex != -1) {
lastIndex = currentIndex;
}
else {
gap = currentIndex - lastIndex - 1;
maxGap = max(gap, maxGap);
lastIndex = currentIndex;
}
}
// Check prev and next nodes for all
// intermediate nodes
else if (pre->data < cur->data
&& next->data < cur->data) {
if (lastIndex != -1) {
lastIndex = currentIndex;
}
else {
gap = currentIndex - lastIndex - 1;
maxGap = max(gap, maxGap);
lastIndex = currentIndex;
}
}
// Move pre and cur pointer
pre = pre->next;
cur = cur->next;
currentIndex++;
}
cout << maxGap << "\n";
}
// Driver code
int main()
{
// Create the linkedlist
Node* head = new Node(1, NULL);
head->next = new Node(2, NULL);
head->next->next = new Node(3, NULL);
head->next->next->next = new Node(1, NULL);
head->next->next->next->next = new Node(5, NULL);
head->next->next->next->next->next = new Node(4, NULL);
head->next->next->next->next->next->next
= new Node(4, NULL);
head->next->next->next->next->next->next->next
= new Node(10, NULL);
head->next->next->next->next->next->next->next->next
= new Node(7, NULL);
// Function call
findMaxGap(head);
}
// This code is contributed by Aneshka Goyal
// Time complexity is O(n) while space is O(1), so no need
// of another data structure
Java
// Java code to implement the above approach
import java.io.*;
import java.util.*;
// Class for the structure of a node
class Node {
int data;
Node next;
public Node(int data, Node next)
{
this.data = data;
this.next = next;
}
}
class GFG {
// Driver code
public static void main(String[] args)
{
// Create the linkedlist
Node head = new Node(1, null);
head.next = new Node(2, null);
head.next.next = new Node(3, null);
head.next.next.next = new Node(1, null);
head.next.next.next.next = new Node(5, null);
head.next.next.next.next.next = new Node(4, null);
head.next.next.next.next.next.next
= new Node(4, null);
head.next.next.next.next.next.next.next
= new Node(10, null);
head.next.next.next.next.next.next.next.next
= new Node(7, null);
// Function call
findMaxGap(head);
}
// Function to find the maximum distance
static void findMaxGap(Node head)
{
// Create a set to store
// all the peak nodes
Set<Node> peaks = new HashSet<>();
// Pre points to previous of current node
Node pre = new Node(-1, head);
// Current is initially head
Node cur = head;
// Loop till current is not null
while (cur != null) {
// Find next of current
Node next = cur.next;
// One node only
if (pre.next == head && next == null)
peaks.add(cur);
// For the 1st node check only next
else if (pre.next == head
&& next.data < cur.data)
peaks.add(cur);
// For the last node check
// only the prev node
else if (next == null
&& pre.data < cur.data)
peaks.add(cur);
// Check prev and next nodes for all
// intermediate nodes
else if (pre.data < cur.data
&& next.data < cur.data)
peaks.add(cur);
// Move pre and cur pointer
pre = pre.next;
cur = cur.next;
}
// Initialize
int lastPeakIndex = -1,
currentIndex = 0,
maxGap = 0, gap = 0;
cur = head;
// Iterate through the linkedlist
while (cur != null) {
// If current node is a peak
if (peaks.contains(cur)) {
// If current node is first peak
// then update lastPeakIndex
// and move ahead
if (lastPeakIndex == -1)
lastPeakIndex = currentIndex;
// If current node peak then
// calculate gap and update
// lastPeakIndex and move ahead
else {
gap = currentIndex
- lastPeakIndex - 1;
maxGap = Math.max(gap, maxGap);
lastPeakIndex = currentIndex;
}
}
// Increment currentIndex
// move current node ahead
currentIndex++;
cur = cur.next;
}
System.out.println(maxGap);
}
}
Python3
# Python Code to implement the above approach class Node: def __init__(self, data, next): self.data = data # Assign data self.next = next # Initialize next as null # Function to find maximum difference def findMaxGap(): # Create a set to store all peak nodes peaks = set() # Pre points to previous of current node pre = Node(-1, head) # Current is pointed to head cur = head while (cur): next_node = cur.next # One node only if(pre.next == head and next_node == None): peaks.add(cur) # For the 1st node check only next elif(pre.next == head and next_node.data < cur.data): peaks.add(cur) # For the last node check # only the prev node elif(next_node == None and pre.data < cur.data): peaks.add(cur) # Check prev and next nodes for all # intermediate nodes elif(pre.data < cur.data and next_node.data < cur.data): peaks.add(cur) pre = pre.next cur = cur.next lastPeakIndex = -1 currentIndex = 0 maxGap = 0 gap = 0 cur = head while (cur): # If current node is a peak if(cur in peaks): # If current node is first peak then # update lastPeakIndex and move ahead if(lastPeakIndex == -1): lastPeakIndex = currentIndex # If current node peak then calculate # gap and update lastPeakIndex and move ahead else: gap = currentIndex-lastPeakIndex-1 maxGap = max(gap, maxGap) lastPeakIndex = currentIndex currentIndex += 1 cur = cur.next print(maxGap) # Create linked list. head = Node(1, None) head.next = Node(2, None) head.next.next = Node(3, None) head.next.next.next = Node(1, None) head.next.next.next.next = Node(5, None) head.next.next.next.next.next = Node(4, None) head.next.next.next.next.next.next = Node(4, None) head.next.next.next.next.next.next.next = Node(10, None) head.next.next.next.next.next.next.next.next = Node(7, None) # function call findMaxGap() # This code is contributed by lokesh (lokeshmvs21).
C#
// C# code to implement the above approach
using System;
using System.Collections.Generic;
// Class for the structure of a node
class Node {
public int data;
public Node next;
public Node(int data, Node next)
{
this.data = data;
this.next = next;
}
}
public class GFG {
// Driver code
public static void Main(String[] args)
{
// Create the linkedlist
Node head = new Node(1, null);
head.next = new Node(2, null);
head.next.next = new Node(3, null);
head.next.next.next = new Node(1, null);
head.next.next.next.next = new Node(5, null);
head.next.next.next.next.next = new Node(4, null);
head.next.next.next.next.next.next
= new Node(4, null);
head.next.next.next.next.next.next.next
= new Node(10, null);
head.next.next.next.next.next.next.next.next
= new Node(7, null);
// Function call
findMaxGap(head);
}
// Function to find the maximum distance
static void findMaxGap(Node head)
{
// Create a set to store
// all the peak nodes
HashSet<Node> peaks = new HashSet<Node>();
// Pre points to previous of current node
Node pre = new Node(-1, head);
// Current is initially head
Node cur = head;
// Loop till current is not null
while (cur != null) {
// Find next of current
Node next = cur.next;
// One node only
if (pre.next == head && next == null)
peaks.Add(cur);
// For the 1st node check only next
else if (pre.next == head
&& next.data < cur.data)
peaks.Add(cur);
// For the last node check
// only the prev node
else if (next == null
&& pre.data < cur.data)
peaks.Add(cur);
// Check prev and next nodes for all
// intermediate nodes
else if (pre.data < cur.data
&& next.data < cur.data)
peaks.Add(cur);
// Move pre and cur pointer
pre = pre.next;
cur = cur.next;
}
// Initialize
int lastPeakIndex = -1,
currentIndex = 0,
maxGap = 0, gap = 0;
cur = head;
// Iterate through the linkedlist
while (cur != null) {
// If current node is a peak
if (peaks.Contains(cur)) {
// If current node is first peak
// then update lastPeakIndex
// and move ahead
if (lastPeakIndex == -1)
lastPeakIndex = currentIndex;
// If current node peak then
// calculate gap and update
// lastPeakIndex and move ahead
else {
gap = currentIndex
- lastPeakIndex - 1;
maxGap = Math.Max(gap, maxGap);
lastPeakIndex = currentIndex;
}
}
// Increment currentIndex
// move current node ahead
currentIndex++;
cur = cur.next;
}
Console.WriteLine(maxGap);
}
}
// This code is contributed by 29AjayKumar
Producción
2
Complejidad temporal: O(N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por amrithabpatil y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA