Dada una lista ordenada con enlaces simples y un valor x, la tarea es encontrar un par cuya suma sea igual a x. No se nos permite usar ningún espacio extra y la complejidad de tiempo esperada es O(n).
Ejemplos:
Input : head = 3-->6-->7-->8-->9-->10-->11 , x=17 Output: (6, 11), (7, 10), (8, 9)
Sugerencia: podemos modificar la lista enlazada original
Una solución simple para este problema es tomar cada elemento uno por uno y recorrer la lista restante en dirección hacia adelante para encontrar el segundo elemento cuya suma sea igual al valor x dado. La complejidad del tiempo para este enfoque será O(n 2 ).
Una solución eficiente para este problema se basa en las ideas discutidas en los siguientes artículos.
Encuentra el par en una lista doblemente enlazada: usamos el mismo algoritmo que atraviesa la lista enlazada desde ambos extremos.
Lista enlazada XOR : en una lista enlazada individualmente, podemos recorrer la lista solo en dirección hacia adelante. Usamos el concepto XOR para convertir una lista con un solo enlace en una lista con doble enlace.
A continuación se muestran los pasos:
- Primero necesitamos convertir nuestra lista de enlaces simples en una lista de enlaces dobles. Aquí se nos da un Node de estructura de lista enlazada individualmente que solo tiene un puntero siguiente , no un puntero anterior , por lo que para convertir nuestra lista enlazada individualmente en una lista enlazada doblemente, usamos una lista enlazada doblemente eficiente en memoria (lista enlazada XOR) .
- En la lista enlazada XOR, cada puntero siguiente de la lista enlazada individualmente contiene XOR de puntero siguiente y anterior .
- Después de convertir una lista enlazada individualmente en una lista doblemente enlazada, inicializamos dos variables de puntero para encontrar los elementos candidatos en la lista doblemente enlazada ordenada. Inicialice primero con el inicio de la lista doblemente enlazada, es decir; primero = cabeza e inicializar segundo con el último Node de la lista doblemente enlazada, es decir; segundo = último_Node .
- Aquí no tenemos acceso aleatorio, por lo que para inicializar el puntero, recorremos la lista hasta el último Node y asignamos el último Node al segundo.
- Si la suma actual de primero y segundo es menor que x, entonces nos movemos primero en dirección hacia adelante. Si la suma actual del primer y segundo elemento es mayor que x, entonces nos movemos en segundo lugar 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í (primero = siguiente_Node), o se vuelven iguales (primero == segundo).
Implementación:
C++
// C++ program to find pair with given sum in a singly
// linked list in O(n) time and no extra space.
#include<bits/stdc++.h>
using namespace std;
/* Link list node */
struct Node
{
int data;
/* also contains XOR of next and
previous node after conversion*/
struct Node* next;
};
/* Given a reference (pointer to pointer) to the head
of a list and an int, push a new node on the front
of the list. */
void insert(struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node =
(struct Node*) malloc(sizeof(struct Node));
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
/* returns XORed value of the node addresses */
struct Node* XOR (struct Node *a, struct Node *b)
{
return (struct Node*) ((uintptr_t) (a) ^ (uintptr_t) (b));
}
// Utility function to convert singly linked list
// into XOR doubly linked list
void convert(struct Node *head)
{
// first we store address of next node in it
// then take XOR of next node and previous node
// and store it in next pointer
struct Node *next_node;
// prev node stores the address of previously
// visited node
struct Node *prev = NULL;
// traverse list and store xor of address of
// next_node and prev node in next pointer of node
while (head != NULL)
{
// address of next node
next_node = head->next;
// xor of next_node and prev node
head->next = XOR(next_node, prev);
// update previous node
prev = head;
// move head forward
head = next_node;
}
}
// function to Find pair whose sum is equal to
// given value x
void pairSum(struct Node *head, int x)
{
// initialize first
struct Node *first = head;
// next_node and prev node to calculate xor again
// and find next and prev node while moving forward
// and backward direction from both the corners
struct Node *next_node = NULL, *prev = NULL;
// traverse list to initialize second pointer
// here we need to move in forward direction so to
// calculate next address we have to take xor
// with prev pointer because (a^b)^b = a
struct Node *second = head;
while (second->next != prev)
{
struct Node *temp = second;
second = XOR(second->next, prev);
prev = temp;
}
// now traverse from both the corners
next_node = NULL;
prev = NULL;
// here if we want to move forward then we must
// know the prev address to calculate next node
// and if we want to move backward then we must
// know the next_node address to calculate prev node
bool flag = false;
while (first != NULL && second != NULL &&
first != second && first != next_node)
{
if ((first->data + second->data)==x)
{
cout << "(" << first->data << ","
<< second->data << ")" << endl;
flag = true;
// move first in forward
struct Node *temp = first;
first = XOR(first->next,prev);
prev = temp;
// move second in backward
temp = second;
second = XOR(second->next, next_node);
next_node = temp;
}
else
{
if ((first->data + second->data) < x)
{
// move first in forward
struct Node *temp = first;
first = XOR(first->next,prev);
prev = temp;
}
else
{
// move second in backward
struct Node *temp = second;
second = XOR(second->next, next_node);
next_node = temp;
}
}
}
if (flag == false)
cout << "No pair found" << endl;
}
// Driver program to run the case
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
int x = 17;
/* Use insert() to construct below list
3-->6-->7-->8-->9-->10-->11 */
insert(&head, 11);
insert(&head, 10);
insert(&head, 9);
insert(&head, 8);
insert(&head, 7);
insert(&head, 6);
insert(&head, 3);
// convert singly linked list into XOR doubly
// linked list
convert(head);
pairSum(head,x);
return 0;
}
Producción:
(6,11) , (7,10) , (8,9)
Complejidad del tiempo : O(n)
Si la lista vinculada no está ordenada, podemos ordenar la lista como primer paso. Pero en ese caso, la complejidad del tiempo general se convertiría en O (n Log n). Podemos usar Hashing en tales casos si el espacio adicional no es una restricción. La solución basada en hash es la misma que el método 2 aquí .
Este artículo es una contribución de Shashank Mishra (Gullu) . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA