Encuentre pares con la suma dada en una lista doblemente enlazada

Dada una lista ordenada doblemente enlazada de elementos distintos positivos, la tarea es encontrar pares en una lista doblemente enlazada cuya suma sea igual al valor dado x, sin usar ningún espacio adicional. 

Ejemplo:  

Input : head : 1 <-> 2 <-> 4 <-> 5 <-> 6 <-> 8 <-> 9
        x = 7
Output: (6, 1), (5,2)

La complejidad temporal esperada es O(n) y el espacio auxiliar es O(1).

Un enfoque simple para este problema es elegir uno por uno cada Node y encontrar un segundo elemento cuya suma sea igual a x en la lista restante al atravesar en la dirección de avance. La complejidad temporal de este problema será O(n^2), n es el número total de Nodes en la 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 comienzo de la lista doblemente enlazada, es decir; first=head e inicializa second 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, así que para encontrar el segundo puntero, recorremos la lista para inicializar el 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 dos punteros se cruzan (segundo->siguiente = primero), o se vuelven iguales (primero == segundo).
• El caso en que no haya pares presentes será manejado por la condición “primero==segundo”

Implementación:

// C++ program to find a pair with given sum x.
#include<bits/stdc++.h>
using namespace std;
 
// structure of node of doubly linked list
struct Node
{
    int data;
    struct Node *next, *prev;
};
 
// Function to find pair whose sum equal to given value x.
void pairSum(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 two pointers
    // cross each other (second->next
    // == first), or they become same (first == second)
    while (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 program
int main()
{
    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 = 7;
 
    pairSum(head, x);
 
    return 0;
}

// Java program to find a
// pair with given sum x.
class GFG
{
 
// structure of node of
// doubly linked list
static class Node
{
    int data;
    Node next, prev;
};
 
// Function to find pair whose
// sum equal to given value x.
static void pairSum( 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 
    // they cross each other (second.next
    // == first), or they become same
    // (first == second)
    while ( 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 temp;
}
 
// Driver Code
public static void main(String args[])
{
    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 = 7;
 
    pairSum(head, x);
}
}
 
// This code is contributed
// by Arnab Kundu

# Python3 program to find a pair with
# given sum x.
 
# Structure of node of doubly linked list
class Node:
     
    def __init__(self, x):
         
        self.data = x
        self.next = None
        self.prev = None
 
# Function to find pair whose sum
# equal to given value x.
def pairSum(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 they
    # cross each other (second.next ==
    # first), or they become same
    # (first == second)
    while (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(data)
     
    if not head:
        head = temp
    else:
        temp.next = head
        head.prev = temp
        head = temp
         
    return head
 
# Driver code
if __name__ == '__main__':
     
    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 = 7
 
    pairSum(head, x)
 
# This code is contributed by mohit kumar 29

// C# program to find a
// pair with given sum x.
using System;
 
class GFG
{
 
    // structure of node of
    // doubly linked list
    class Node
    {
        public int data;
        public Node next, prev;
    };
 
    // Function to find pair whose
    // sum equal to given value x.
    static void pairSum( 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 
        // they cross each other (second.next
        // == first), or they become same
        // (first == second)
        while (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 temp;
    }
 
    // Driver Code
    public static void Main(String []args)
    {
        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 = 7;
 
        pairSum(head, x);
    }
}
 
// This code is contributed by 29AjayKumar

<script>
// Javascript program to find a
// pair with given sum x.
 
// structure of node of
// doubly linked list
class Node
{
    constructor()
    {
        this.data = 0;
        this.next = this.prev = null;
    }
}
 
// Function to find pair whose
// sum equal to given value x.
function pairSum(head, x)
{
 
    // Set two pointers, first
    // to the beginning of DLL
    // and second to the end of DLL.
    let first = head;
    let second = head;
    while (second.next != null)
        second = second.next;
  
    // To track if we find a pair or not
    let found = false;
  
    // The loop terminates when
    // they cross each other (second.next
    // == first), or they become same
    // (first == second)
    while ( 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<br>");
}
 
// A utility function to insert
// a new node at the beginning
// of doubly linked list
function insert(head,data)
{
    let 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 temp;
}
 
// Driver Code
let 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);
let x = 7;
 
pairSum(head, x);
 
// This code is contributed by avanitrachhadiya2155
</script>

(1, 6)
(2, 5)

Complejidad temporal : O(n) 
Espacio auxiliar : O(1)

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 le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo usando contribuya.geeksforgeeks.org o envíe su 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.