Encuentre un elemento de pico en la lista enlazada

Posted on by Rudeus Greyrat

Dada una lista enlazada de enteros. La tarea es encontrar un elemento pico en él. Se dice que un elemento de la lista es pico si NO es más pequeño que sus vecinos. Para elementos de esquina, debemos considerar solo un vecino. Por ejemplo: 
 

  • Si la lista de entrada es {5 -> 10 -> 20 -> 15}, 20 es el único elemento de pico.
  • Para la lista de entrada {10 -> 20 -> 15 -> 2 -> 23 -> 90 -> 67}, hay dos elementos de pico: 20 y 90. Tenga en cuenta que es necesario devolver cualquier elemento de pico.

Los siguientes casos de esquina dan una mejor idea sobre el problema: 
 

  1. Si la lista de entrada se ordena en orden estrictamente creciente, el último elemento es siempre un elemento de pico. Por ejemplo, 50 es el elemento pico en {10 -> 20 -> 30 -> 40 -> 50}.
  2. Si la lista de entrada se ordena estrictamente decreciente, el primer elemento es siempre un elemento de pico. 100 es el elemento pico en {100 -> 80 -> 60 -> 50 -> 20}.
  3. Si todos los elementos de la lista de entrada son iguales, cada elemento es un elemento de pico.

Ejemplos : 
 

Input : List =  {1 -> 6 -> 8 -> 4 -> 12}
Output : 8

Input : List = {10 -> 20 -> 15 -> 2 -> 23 -> 90 -> 67}
Output : 90

La idea es recorrer la lista enlazada y verificar si el elemento actual es un elemento pico o no. En caso afirmativo, devuelva el elemento actual; de lo contrario, avance en la lista.
El elemento actual será un elemento pico si es mayor que sus elementos anterior y siguiente.
El siguiente programa ilustra el enfoque anterior: 
 

C++

// C++ implementation to find the peak
// element in the Linked List
#include <bits/stdc++.h>
using namespace std;
 
/* A Linked list node */
struct Node {
    int data;
    struct Node* next;
};
 
// function to insert a node at the
// beginning of the linked list
void push(struct Node** head_ref, int new_data)
{
    struct Node* new_node = new Node;
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}
 
// Function to find the peak element
int findPeak(struct Node* head)
{
    // Return -1 to indicate that
    // peak does not exist
    if (head == NULL)
        return -1;
 
    // If there is only one node
    if (head->next == NULL)
        return head->data;
 
    // Traverse till last node (starting from
    // second node)
    int prev = head->data;
    Node *curr;
    for (curr = head->next; curr->next != NULL;
         curr = curr->next) {
 
        // check if current node is greater
        // than both neighbours
        if (curr->data > curr->next->data
            && curr->data > prev)
            return curr->data;
 
        prev = curr->data;
    }
 
    // We reach here when curr is last node
    if (curr->data > prev)
        return curr->data;
 
    // Peak does not exists
    else
        return -1;
}
 
// Driver program
int main()
{
    struct Node* head = NULL;
 
    // create linked list 1->6->8->4->12
    push(&head, 12);
    push(&head, 4);
    push(&head, 8);
    push(&head, 6);
    push(&head, 1);
 
    cout << "Peak element is: "
         << findPeak(head);
 
    return 0;
}

Java

// Java implementation to find the peak
// element in the Linked List
class GFG
{
     
// A Linked list node /
static class Node
{
    int data;
    Node next;
};
 
// function to insert a node at the
// beginning of the linked list
static Node push( Node head_ref, int new_data)
{
    Node new_node = new Node();
    new_node.data = new_data;
    new_node.next = (head_ref);
    (head_ref) = new_node;
    return head_ref;
}
 
// Function to find the peak element
static int findPeak( Node head)
{
    // Return -1 to indicate that
    // peak does not exist
    if (head == null)
        return -1;
 
    // If there is only one node
    if (head.next == null)
        return head.data;
 
    // Traverse till last node (starting from
    // second node)
    int prev = head.data;
    Node curr;
    for (curr = head.next; curr.next != null;
        curr = curr.next)
    {
 
        // check if current node is greater
        // than both neighbours
        if (curr.data > curr.next.data
            && curr.data > prev)
            return curr.data;
 
        prev = curr.data;
    }
 
    // We reach here when curr is last node
    if (curr.data > prev)
        return curr.data;
 
    // Peak does not exists
    else
        return -1;
}
 
// Driver program
public static void main(String args[])
{
    Node head = null;
 
    // create linked list 1.6.8.4.12
    head=push(head, 12);
    head=push(head, 4);
    head=push(head, 8);
    head=push(head, 6);
    head=push(head, 1);
 
    System.out.print("Peak element is: "
        + findPeak(head));
}
}
 
// This code is contributed by Arnab Kundu

Python3

# Python3 implementation to find the peak
# element in the Linked List
 
# Link list node
class Node :
    def __init__(self):
        self.data = 0
        self.next = None
 
# function to insert a node at the
# beginning of the linked list
def push( head_ref, new_data) :
 
    new_node = Node()
    new_node.data = new_data
    new_node.next = (head_ref)
    (head_ref) = new_node
    return head_ref
 
# Function to find the peak element
def findPeak( head):
 
    # Return -1 to indicate that
    # peak does not exist
    if (head == None) :
        return -1
 
    # If there is only one node
    if (head.next == None) :
        return head.data
 
    # Traverse till last node (starting from
    # second node)
    prev = head.data
    curr = head.next
    while( curr.next != None ):
     
        # check if current node is greater
        # than both neighbours
        if (curr.data > curr.next.data and curr.data > prev) :
            return curr.data
 
        prev = curr.data
        curr = curr.next
 
    # We reach here when curr is last node
    if (curr.data > prev) :
        return curr.data
 
    # Peak does not exists
    else:
        return -1
 
# Driver program
 
head = None
 
# create linked list 1.6.8.4.12
head = push(head, 12)
head = push(head, 4)
head = push(head, 8)
head = push(head, 6)
head = push(head, 1)
 
print("Peak element is: ", findPeak(head))
 
# This code is contributed by Arnab Kundu

C#

// C# implementation to find the peak
// element in the Linked List
using System;
 
class GFG
{
     
// A Linked list node /
public class Node
{
    public int data;
    public Node next;
};
 
// function to insert a node at the
// beginning of the linked list
static Node push(Node head_ref, int new_data)
{
    Node new_node = new Node();
    new_node.data = new_data;
    new_node.next = (head_ref);
    (head_ref) = new_node;
    return head_ref;
}
 
// Function to find the peak element
static int findPeak(Node head)
{
    // Return -1 to indicate that
    // peak does not exist
    if (head == null)
        return -1;
 
    // If there is only one node
    if (head.next == null)
        return head.data;
 
    // Traverse till last node
    // (starting from second node)
    int prev = head.data;
    Node curr;
    for (curr = head.next; curr.next != null;
         curr = curr.next)
    {
 
        // check if current node is greater
        // than both neighbours
        if (curr.data > curr.next.data
            && curr.data > prev)
            return curr.data;
 
        prev = curr.data;
    }
 
    // We reach here when curr is last node
    if (curr.data > prev)
        return curr.data;
 
    // Peak does not exists
    else
        return -1;
}
 
// Driver Code
public static void Main(String[] args)
{
    Node head = null;
 
    // create linked list 1.6.8.4.12
    head = push(head, 12);
    head = push(head, 4);
    head = push(head, 8);
    head = push(head, 6);
    head = push(head, 1);
 
    Console.Write("Peak element is: " +
                   findPeak(head));
}
}
 
// This code is contributed by Rajput-Ji

Javascript

<script>
 
      // JavaScript implementation to find the peak
      // element in the Linked List
      // A Linked list node /
      class Node {
        constructor() {
          this.data = 0;
          this.next = null;
        }
      }
 
      // function to insert a node at the
      // beginning of the linked list
      function push(head_ref, new_data) {
        var new_node = new Node();
        new_node.data = new_data;
        new_node.next = head_ref;
        head_ref = new_node;
        return head_ref;
      }
 
      // Function to find the peak element
      function findPeak(head) {
        // Return -1 to indicate that
        // peak does not exist
        if (head == null) return -1;
 
        // If there is only one node
        if (head.next == null) return head.data;
 
        // Traverse till last node
        // (starting from second node)
        var prev = head.data;
        var curr;
        for (curr = head.next; curr.next != null; curr = curr.next)
        {
          // check if current node is greater
          // than both neighbours
          if (curr.data > curr.next.data && curr.data > prev)
          return curr.data;
 
          prev = curr.data;
        }
 
        // We reach here when curr is last node
        if (curr.data > prev) return curr.data;
        // Peak does not exists
        else return -1;
      }
 
      // Driver Code
      var head = null;
 
      // create linked list 1.6.8.4.12
      head = push(head, 12);
      head = push(head, 4);
      head = push(head, 8);
      head = push(head, 6);
      head = push(head, 1);
 
      document.write("Peak element is: " + findPeak(head));
       
</script>
Producción: 

Peak element is: 8

 

Publicación traducida automáticamente

Artículo escrito por barykrg y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *