Dada una lista ordenada doblemente enlazada de elementos distintos positivos , la tarea es encontrar pares en la lista doblemente enlazada cuyo producto sea igual al valor dado x, sin usar ningún espacio extra.
Ejemplos :
Input : List = 1 <=> 2 <=> 4 <=> 5 <=> 6 <=> 8 <=> 9
x = 8
Output: (1, 8), (2, 4)
Input : List = 1 <=> 2 <=> 3 <=> 4 <=> 5 <=> 6 <=> 7
x = 6
Output: (1, 6), (2, 3)
Un enfoque simple para este problema es recorrer la lista enlazada usando dos bucles anidados y encontrar todos los pares y verificar los pares con el producto igual a x. La complejidad del tiempo para este problema será O(n^2), n es el número total de Nodes en una lista doblemente enlazada.
Una solución eficiente para este problema es la misma que en este artículo. Aquí está el algoritmo:
- Inicialice dos variables de puntero para encontrar los elementos candidatos en la lista ordenada doblemente enlazada. Inicialice primero con el inicio de la lista doblemente enlazada, es decir; first=head e inicializa el segundo con el último Node de la lista doblemente enlazada, es decir; segundo=último_Node .
- Inicializamos los punteros primero y segundo como primer y último Node. Aquí no tenemos acceso aleatorio, por lo que para encontrar el segundo puntero, recorremos la lista para inicializar el segundo.
- Si el producto actual de primero y segundo es menor que x, entonces nos movemos primero hacia adelante. Si el producto actual del primer y segundo elemento es mayor que x, entonces movemos el segundo en dirección hacia atrás.
- Las condiciones de terminación de bucle también son diferentes de las arrays. El ciclo termina cuando cualquiera de los dos punteros se convierte en NULL, o se cruzan entre sí (segundo->siguiente = primero), o se vuelven iguales (primero == segundo)
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to find a pair with
// given product x in sorted Doubly
// Linked List
#include <bits/stdc++.h>
using namespace std;
// Doubly Linked List Node
struct Node {
int data;
struct Node *next, *prev;
};
// Function to find pair whose product
// equal to given value x
void pairProduct(struct Node* head, int x)
{
// Set two pointers,
// first to the beginning of DLL
// and second to the end of DLL.
struct Node* first = head;
struct Node* second = head;
while (second->next != NULL)
second = second->next;
// To track if we find a pair or not
bool found = false;
// The loop terminates when either of two pointers
// become NULL, or they cross each other (second->next
// == first), or they become same (first == second)
while (first != NULL && second != NULL && first != second
&& second->next != first) {
// pair found
if ((first->data * second->data) == x) {
found = true;
cout << "(" << first->data << ", "
<< second->data << ")" << endl;
// move first in forward direction
first = first->next;
// move second in backward direction
second = second->prev;
}
else {
if ((first->data * second->data) < x)
first = first->next;
else
second = second->prev;
}
}
// if pair is not present
if (found == false)
cout << "No pair found";
}
// A utility function to insert a new node at the
// beginning of doubly linked list
void insert(struct Node** head, int data)
{
struct Node* temp = new Node;
temp->data = data;
temp->next = temp->prev = NULL;
if (!(*head))
(*head) = temp;
else {
temp->next = *head;
(*head)->prev = temp;
(*head) = temp;
}
}
// Driver Code
int main()
{
// Create Doubly Linked List
struct Node* head = NULL;
insert(&head, 9);
insert(&head, 8);
insert(&head, 6);
insert(&head, 5);
insert(&head, 4);
insert(&head, 2);
insert(&head, 1);
int x = 8;
pairProduct(head, x);
return 0;
}
Java
// Java program to find a pair with
// given product x in sorted Doubly
// Linked List
class GFG {
// Doubly Linked List Node
static class Node {
int data;
Node next, prev;
};
// Function to find pair whose product
// equal to given value x
static void pairProduct(Node head, int x)
{
// Set two pointers,
// first to the beginning of DLL
// and second to the end of DLL.
Node first = head;
Node second = head;
while (second.next != null)
second = second.next;
// To track if we find a pair or not
boolean found = false;
// The loop terminates when either of two pointers
// become null, or they cross each other (second.next
// == first), or they become same (first == second)
while (first != null && second != null && first != second
&& second.next != first) {
// pair found
if ((first.data * second.data) == x) {
found = true;
System.out.println("(" + first.data + ", "
+ second.data + ")");
// move first in forward direction
first = first.next;
// move second in backward direction
second = second.prev;
}
else {
if ((first.data * second.data) < x)
first = first.next;
else
second = second.prev;
}
}
// if pair is not present
if (found == false)
System.out.println("No pair found");
}
// A utility function to insert a new node at the
// beginning of doubly linked list
static Node insert(Node head, int data)
{
Node temp = new Node();
temp.data = data;
temp.next = temp.prev = null;
if ((head) == null)
(head) = temp;
else {
temp.next = head;
(head).prev = temp;
(head) = temp;
}
return head;
}
// Driver Code
public static void main(String args[])
{
// Create Doubly Linked List
Node head = null;
head = insert(head, 9);
head = insert(head, 8);
head = insert(head, 6);
head = insert(head, 5);
head = insert(head, 4);
head = insert(head, 2);
head = insert(head, 1);
int x = 8;
pairProduct(head, x);
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 program to find a pair with
# given product x in sorted Doubly
# Linked List
# Node of the doubly linked list
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
# Function to find pair whose product
# equal to given value x
def pairProduct(head, x):
# Set two pointers,
# first to the beginning of DLL
# and second to the end of DLL.
first = head
second = head
while (second.next != None):
second = second.next
# To track if we find a pair or not
found = False
# The loop terminates when either of two pointers
# become None, or they cross each other (second.next
# == first), or they become same (first == second)
while (first != None and second != None and
first != second and second.next != first) :
# pair found
if ((first.data * second.data) == x) :
found = True
print("(", first.data, ", ", second.data, ")")
# move first in forward direction
first = first.next
# move second in backward direction
second = second.prev
else :
if ((first.data * second.data) < x):
first = first.next
else:
second = second.prev
# if pair is not present
if (found == False):
print( "No pair found")
# A utility function to insert a new node at the
# beginning of doubly linked list
def insert(head, data):
temp = Node(0)
temp.data = data
temp.next = temp.prev = None
if (head == None):
(head) = temp
else :
temp.next = head
(head).prev = temp
(head) = temp
return head
# Driver Code
if __name__ == "__main__":
# Create Doubly Linked List
head = None
head = insert(head, 9)
head = insert(head, 8)
head = insert(head, 6)
head = insert(head, 5)
head = insert(head, 4)
head = insert(head, 2)
head = insert(head, 1)
x = 8
pairProduct(head, x)
# This code is contributed by Arnab Kundu
C#
// C# program to find a pair with
// given product x in sorted Doubly
// Linked List
using System;
class GFG {
// Doubly Linked List Node
public class Node {
public int data;
public Node next, prev;
};
// Function to find pair whose product
// equal to given value x
static void pairProduct(Node head, int x)
{
// Set two pointers,
// first to the beginning of DLL
// and second to the end of DLL.
Node first = head;
Node second = head;
while (second.next != null)
second = second.next;
// To track if we find a pair or not
bool found = false;
// The loop terminates when either of two pointers
// become null, or they cross each other (second.next
// == first), or they become same (first == second)
while (first != null && second != null && first != second
&& second.next != first) {
// pair found
if ((first.data * second.data) == x) {
found = true;
Console.WriteLine("(" + first.data + ", "
+ second.data + ")");
// move first in forward direction
first = first.next;
// move second in backward direction
second = second.prev;
}
else {
if ((first.data * second.data) < x)
first = first.next;
else
second = second.prev;
}
}
// if pair is not present
if (found == false)
Console.WriteLine("No pair found");
}
// A utility function to insert a new node at the
// beginning of doubly linked list
static Node insert(Node head, int data)
{
Node temp = new Node();
temp.data = data;
temp.next = temp.prev = null;
if ((head) == null)
(head) = temp;
else {
temp.next = head;
(head).prev = temp;
(head) = temp;
}
return head;
}
// Driver Code
public static void Main(String[] args)
{
// Create Doubly Linked List
Node head = null;
head = insert(head, 9);
head = insert(head, 8);
head = insert(head, 6);
head = insert(head, 5);
head = insert(head, 4);
head = insert(head, 2);
head = insert(head, 1);
int x = 8;
pairProduct(head, x);
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// javascript program to find a pair with
// given product x in sorted Doubly
// Linked List
// Doubly Linked List Node
class Node {
constructor() {
this.data = 0;
this.prev = null;
this.next = null;
}
}
// Function to find pair whose product
// equal to given value x
function pairProduct( head , x) {
// Set two pointers,
// first to the beginning of DLL
// and second to the end of DLL.
first = head;
second = head;
while (second.next != null)
second = second.next;
// To track if we find a pair or not
var found = false;
// The loop terminates when either of two pointers
// become null, or they cross each other (second.next
// == first), or they become same (first == second)
while (first != null && second != null && first != second && second.next != first) {
// pair found
if ((first.data * second.data) == x) {
found = true;
document.write("(" + first.data + ", " + second.data + ")<br/>");
// move first in forward direction
first = first.next;
// move second in backward direction
second = second.prev;
} else {
if ((first.data * second.data) < x)
first = first.next;
else
second = second.prev;
}
}
// if pair is not present
if (found == false)
document.write("No pair found");
}
// A utility function to insert a new node at the
// beginning of doubly linked list
function insert( head , data) {
temp = new Node();
temp.data = data;
temp.next = temp.prev = null;
if ((head) == null)
(head) = temp;
else {
temp.next = head;
(head).prev = temp;
(head) = temp;
}
return head;
}
// Driver Code
// Create Doubly Linked List
head = null;
head = insert(head, 9);
head = insert(head, 8);
head = insert(head, 6);
head = insert(head, 5);
head = insert(head, 4);
head = insert(head, 2);
head = insert(head, 1);
var x = 8;
pairProduct(head, x);
// This code contributed by aashish1995
</script>
Producción:
(1, 8) (2, 4)
Complejidad del tiempo : O(n)
Publicación traducida automáticamente
Artículo escrito por VishalBachchas y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA