Dada una lista enlazada con elementos distintos, la tarea es encontrar el punto bitónico en la lista enlazada dada. Si no existe tal punto, imprima -1 .
Ejemplos:
Entrada: 1 -> 2 -> 3 -> 4 -> 3 -> 2 -> 1 -> NULL
Salida: 4
1 -> 2 -> 3 -> 4 es estrictamente creciente.
4 -> 3 -> 2 -> 1 -> NULL es estrictamente decreciente.
Entrada: 97 -> 98 -> 99 -> 91 -> NULO
Salida: 99
Enfoque: Un punto bitónico es un punto en secuencia bitónica antes del cual los elementos son estrictamente crecientes y después del cual los elementos son estrictamente decrecientes. Un punto bitónico no existe si la array solo disminuye o solo aumenta. Entonces, encuentre el primer Node tal que el valor del Node al lado sea estrictamente menor. Comience a recorrer la lista vinculada desde ese Node en adelante y si todos los demás Nodes son estrictamente más pequeños que su Node anterior, entonces el Node encontrado estaba fuera de la secuencia bitónica; de lo contrario, la lista vinculada dada no contiene una secuencia bitónica válida. Tenga en cuenta que una lista vacía o una lista con un solo Node no representa una secuencia bitónica válida.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
// Node for linked list
class Node {
public:
int data;
Node* next;
};
// Function to insert a node at
// the head of the linked list
Node* push(Node** head_ref, int data)
{
Node* new_node = new Node;
new_node->data = data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
// Function to return the bitonic
// of the given linked list
int bitonic_point(Node* node)
{
// If list is empty
if (node == NULL)
return -1;
// If list contains only
// a single node
if (node->next == NULL)
return -1;
// Invalid bitonic sequence
if (node->data > node->next->data)
return -1;
while (node->next != NULL) {
// If current node is the bitonic point
if (node->data > node->next->data)
break;
// Get to the next node in the list
node = node->next;
}
int bitonicPoint = node->data;
// Nodes must be in descending
// starting from here
while (node->next != NULL) {
// Out of order node
if (node->data < node->next->data)
return -1;
// Get to the next node in the list
node = node->next;
}
return bitonicPoint;
}
// Driver code
int main()
{
Node* head = NULL;
push(&head, 100);
push(&head, 201);
push(&head, 399);
push(&head, 490);
push(&head, 377);
push(&head, 291);
push(&head, 100);
cout << bitonic_point(head);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Node for linked list
static class Node
{
int data;
Node next;
};
// Function to insert a node at
// the head of the linked list
static Node push(Node head_ref, int data)
{
Node new_node = new Node();
new_node.data = data;
new_node.next = (head_ref);
(head_ref) = new_node;
return head_ref;
}
// Function to return the bitonic
// of the given linked list
static int bitonic_point(Node node)
{
// If list is empty
if (node == null)
return -1;
// If list contains only
// a single node
if (node.next == null)
return -1;
// Invalid bitonic sequence
if (node.data > node.next.data)
return -1;
while (node.next != null)
{
// If current node is the bitonic point
if (node.data > node.next.data)
break;
// Get to the next node in the list
node = node.next;
}
int bitonicPoint = node.data;
// Nodes must be in descending
// starting from here
while (node.next != null)
{
// Out of order node
if (node.data < node.next.data)
return -1;
// Get to the next node in the list
node = node.next;
}
return bitonicPoint;
}
// Driver code
public static void main(String args[])
{
Node head = null;
head=push(head, 100);
head=push(head, 201);
head=push(head, 399);
head=push(head, 490);
head=push(head, 377);
head=push(head, 291);
head=push(head, 100);
System.out.println(bitonic_point(head));
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 implementation of the approach # Node for linked list class Node: def __init__(self, data): self.data = data self.next = None # Function to insert a node at # the head of the linked list def push(head_ref, data): new_node = Node(data) new_node.next = head_ref head_ref = new_node return head_ref # Function to return the bitonic # of the given linked list def bitonic_point(node): # If list is empty if (node == None): return -1; # If list contains only # a single node if (node.next == None): return -1; # Invalid bitonic sequence if (node.data > node.next.data): return -1; while (node.next != None): # If current node is the bitonic point if (node.data > node.next.data): break; # Get to the next node in the list node = node.next; bitonicPoint = node.data; # Nodes must be in descending # starting from here while (node.next != None): # Out of order node if (node.data < node.next.data): return -1; # Get to the next node in the list node = node.next; return bitonicPoint; # Driver code if __name__=='__main__': head = None; head = push(head, 100); head = push(head, 201); head = push(head, 399); head = push(head, 490); head = push(head, 377); head = push(head, 291); head = push(head, 100); print(bitonic_point(head)) # This code is contributed by rutvik_56
C#
// C# implementation of the approach
using System;
class GFG
{
// Node for linked list
public class Node
{
public int data;
public Node next;
};
// Function to insert a node at
// the head of the linked list
static Node push(Node head_ref, int data)
{
Node new_node = new Node();
new_node.data = data;
new_node.next = (head_ref);
(head_ref) = new_node;
return head_ref;
}
// Function to return the bitonic
// of the given linked list
static int bitonic_point(Node node)
{
// If list is empty
if (node == null)
return -1;
// If list contains only
// a single node
if (node.next == null)
return -1;
// Invalid bitonic sequence
if (node.data > node.next.data)
return -1;
while (node.next != null)
{
// If current node is the bitonic point
if (node.data > node.next.data)
break;
// Get to the next node in the list
node = node.next;
}
int bitonicPoint = node.data;
// Nodes must be in descending
// starting from here
while (node.next != null)
{
// Out of order node
if (node.data < node.next.data)
return -1;
// Get to the next node in the list
node = node.next;
}
return bitonicPoint;
}
// Driver code
public static void Main(String []args)
{
Node head = null;
head=push(head, 100);
head=push(head, 201);
head=push(head, 399);
head=push(head, 490);
head=push(head, 377);
head=push(head, 291);
head=push(head, 100);
Console.WriteLine(bitonic_point(head));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript implementation of the approach
// Node for linked list
class Node {
constructor() {
this.data = 0;
this.next = null;
}
}
// Function to insert a node at
// the head of the linked list
function push( head_ref, data)
{
var new_node = new Node();
new_node.data = data;
new_node.next = (head_ref);
(head_ref) = new_node;
return head_ref;
}
// Function to return the bitonic
// of the given linked list
function bitonic_point( node)
{
// If list is empty
if (node == null)
return -1;
// If list contains only
// a single node
if (node.next == null)
return -1;
// Invalid bitonic sequence
if (node.data > node.next.data)
return -1;
while (node.next != null)
{
// If current node is the bitonic point
if (node.data > node.next.data)
break;
// Get to the next node in the list
node = node.next;
}
let bitonicPoint = node.data;
// Nodes must be in descending
// starting from here
while (node.next != null)
{
// Out of order node
if (node.data < node.next.data)
return -1;
// Get to the next node in the list
node = node.next;
}
return bitonicPoint;
}
// Driver Code
var head = null;
head=push(head, 100);
head=push(head, 201);
head=push(head, 399);
head=push(head, 490);
head=push(head, 377);
head=push(head, 291);
head=push(head, 100);
document.write(bitonic_point(head));
</script>
Producción:
490