Encuentre cuatrillizos con una suma dada en una lista doblemente enlazada

Dada una lista ordenada doblemente enlazada y un entero X , la tarea es imprimir todos los cuatrillizos en la lista doblemente enlazada cuya suma es X .

Ejemplos:

Entrada: LL: -3 ↔ 1 ↔ 2 ↔ 3 ↔ 5 ↔ 6, X = 7
Salida:
-3 2 3 5 
-3 3 1 6
Explicación: Los cuatrillizos que tienen suma 7( = X) son: {-3, 2 , 3, 5}, {-3, 3, 1, 6}.

Entrada: LL:-2 ↔ -1 ↔ 0 ↔ 0 ↔ 1 ↔ 2, X = 0
Salida:
-2 -1 1 2
-2 0 0 2 
-1 0 0 1

Enfoque: el problema dado se puede resolver usando la idea discutida en este artículo usando la técnica de 4 punteros . Siga los pasos a continuación para resolver el problema:

  • Inicialice cuatro variables, digamos primero como el comienzo de la lista doblemente enlazada, es decir; first = head , segundo al siguiente del primer puntero, tercero al siguiente del segundo puntero y cuarto al último Node de una lista doblemente enlazada que almacena los 4 elementos en la lista ordenada doblemente enlazada.
  • Iterar un ciclo hasta que el primer Node y el cuarto Node no sean NULL , y no sean iguales y estos 2 Nodes no se crucen entre sí y realice los siguientes pasos:
    • Inicialice el segundo puntero al siguiente del primero .
    • Iterar un ciclo hasta que el segundo y el cuarto Node no sean NULL , no sean iguales y no se crucen entre sí.
      • Inicialice una variable, diga suma como (X – (primero → datos + segundo → datos)) , apunte el tercer puntero al siguiente del segundo puntero y tome otro puntero temporal inicializado al último Node , es decir, el cuarto puntero .
      • Iterar un ciclo mientras temp y el tercero no son NULL , no son iguales y no se cruzan entre sí
        • Si el valor de la suma es tercero→datos + temp→datos , imprima el cuádruple e incremente el tercer puntero al siguiente del tercer puntero actual y la temperatura al anterior de la temperatura actual.
        • Si el valor de sum es menor que el tercero→datos + temp→datos , entonces incremente el tercer puntero, es decir, tercero = tercero→siguiente .
        • De lo contrario, disminuya el puntero temporal , es decir, temp = temp→prev .
      • Mueva el segundo puntero a su siguiente puntero.
    • Mueva el primer puntero a su siguiente puntero.

A continuación se muestra la implementación del enfoque anterior:

C++

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Structure of node of a doubly
// linked list
struct Node {
    int data;
    struct Node *next, *prev;
};
 
// Function to insert a new node at
// the beginning of the doubly linked
// list
void insert(struct Node** head, int data)
{
    // Allocate the node
    struct Node* temp = new Node();
 
    // Fill in the data value
    temp->data = data;
    temp->next = temp->prev = NULL;
 
    if ((*head) == NULL)
        (*head) = temp;
    else {
        temp->next = *head;
        (*head)->prev = temp;
        (*head) = temp;
    }
}
 
// Function to print the quadruples
// having sum equal to x
void PrintFourSum(struct Node* head, int x)
{
    // First pointer to the head node
    struct Node* first = head;
 
    // Pointer to point to the second
    // node for the required sum
    struct Node* second;
 
    // Pointer to point to the third
    // node for the required sum
    struct Node* third;
 
    // Fourth points to the last node
    struct Node* fourth = head;
 
    // Update the fourth pointer to
    // the end of the DLL
    while (fourth->next != NULL) {
        fourth = fourth->next;
    }
 
    // Node to point to the fourth node
    // of the required sum
    struct Node* temp;
 
    while (first != NULL
           && fourth != NULL
           && first != fourth
           && fourth->next != first) {
 
        // Point the second node to the
        // second element of quadruple
        second = first->next;
 
        while (second != NULL
               && fourth != NULL
               && second != fourth
               && fourth->next != second) {
 
            int reqsum = x - (first->data
                              + second->data);
 
            // Points to the 3rd element
            // of quadruple
            third = second->next;
 
            // Points to the tail of the DLL
            temp = fourth;
 
            while (third != NULL && temp != NULL
                   && third != temp
                   && temp->next != third) {
 
                // Store the current sum
                int twosum = third->data
                             + temp->data;
 
                // If the sum is equal,
                // then print quadruple
                if (twosum == reqsum) {
 
                    cout << "(" << first->data
                         << ", "
                         << second->data
                         << ", "
                         << third->data
                         << ", "
                         << temp->data
                         << ")\n";
 
                    third = third->next;
                    temp = temp->prev;
                }
 
                // If twosum is less than
                // the reqsum then move the
                // third pointer to the next
                else if (twosum < reqsum) {
                    third = third->next;
                }
 
                // Otherwise move the fourth
                // pointer to the previous
                // of the fourth pointer
                else {
                    temp = temp->prev;
                }
            }
 
            // Move to the next of
            // the second pointer
            second = second->next;
        }
 
        // Move to the next of
        // the first pointer
        first = first->next;
    }
}
 
// Driver Code
int main()
{
    struct Node* head = NULL;
    insert(&head, 2);
    insert(&head, 1);
    insert(&head, 0);
    insert(&head, 0);
    insert(&head, -1);
    insert(&head, -2);
    int X = 0;
    PrintFourSum(head, X);
 
    return 0;
}

Java

// Java program for the above approach
 
class GFG {
 
    // structure of node of
    // doubly linked list
    static class Node {
        int data;
        Node next, prev;
    };
 
    // A utility function to insert
    // a new node at the beginning
    // of the doubly linked list
    static Node insert(Node head, int data)
    {
 
        // Allocate the node
        Node temp = new Node();
 
        // Fill in the data value
        temp.data = data;
        temp.next = temp.prev = null;
        if (head == null)
            (head) = temp;
        else {
            temp.next = head;
            (head).prev = temp;
            (head) = temp;
        }
        return temp;
    }
 
    // Function to print the quadruples
    // having sum equal to x
    static void PrintFourSum(Node head, int x)
    {
 
        // First pointer to the head node
        Node first = head;
 
        // Pointer to point to the second
        // node for the required sum
        Node second = head;
 
        // Pointer to point to the third
        // node for the required sum
        Node third = head;
 
        // Fourth points to the last node
        Node fourth = head;
 
        // Update the fourth pointer to
        // the end of the DLL
        while (fourth.next != null) {
            fourth = fourth.next;
        }
 
        // Node to point to the fourth node
        // of the required sum
        Node temp;
        while (first != null && fourth != null
               && first != fourth && fourth.next != first) {
 
            // Point the second node to the
            // second element of quadruple
            second = first.next;
 
            while (second != null && fourth != null
                   && second != fourth
                   && fourth.next != second) {
 
                int reqsum = x - (first.data + second.data);
 
                // Points to the 3rd element
                // of quadruple
                third = second.next;
 
                // Points to the tail of the DLL
                temp = fourth;
 
                while (third != null && temp != null
                       && third != temp
                       && temp.next != third) {
 
                    // Store the current sum
                    int twosum = third.data + temp.data;
 
                    // If the sum is equal,
                    // then print quadruple
                    if (twosum == reqsum) {
 
                        System.out.println(
                            "(" + first.data + ", "
                            + second.data + ", "
                            + third.data + ", " + temp.data
                            + ")");
 
                        third = third.next;
                        temp = temp.prev;
                    }
 
                    // If twosum is less than
                    // the reqsum then move the
                    // third pointer to the next
                    else if (twosum < reqsum) {
                        third = third.next;
                    }
 
                    // Otherwise move the fourth
                    // pointer to the previous
                    // of the fourth pointer
                    else {
                        temp = temp.prev;
                    }
                }
 
                // Move to the next of
                // the second pointer
                second = second.next;
            }
 
            // Move to the next of
            // the first pointer
            first = first.next;
        }
    }
 
    // Driver Code
    public static void main(String args[])
    {
 
        Node head = null;
        head = insert(head, 2);
        head = insert(head, 1);
        head = insert(head, 0);
        head = insert(head, 0);
        head = insert(head, -1);
        head = insert(head, -2);
        int x = 0;
 
        PrintFourSum(head, x);
    }
}
 
// This code is contributed
// by kirtishsurangalikar

Python3

# Python3 program for the above approach
 
# Structure of node of a doubly
# linked list
class Node:
     
    def __init__(self, d):
         
        self.data = d
        self.left = None
        self.right = None
 
# Function to insert a new node at
# the beginning of the doubly linked
# list
def insert(head, data):
     
    # Allocate the node
    temp = Node(data)
 
    # Fill in the data value
    temp.data = data
    temp.next = temp.prev = None
 
    if (head == None):
        head = temp
    else:
        temp.next = head
        head.prev = temp
        head = temp
 
    return head
 
# Function to print the quadruples
# having sum equal to x
def PrintFourSum(head, x):
     
    # First pointer to the head node
    first = head
 
    # Pointer to point to the second
    # node for the required sum
    second = None
 
    # Pointer to point to the third
    # node for the required sum
    third = None
 
    # Fourth points to the last node
    fourth = head
 
    # Update the fourth pointer to
    # the end of the DLL
    while (fourth.next != None):
        fourth = fourth.next
 
    # Node to point to the fourth node
    # of the required sum
    temp = None
 
    while (first != None and
          fourth != None and
           first != fourth and
     fourth.next != first):
 
        # Point the second node to the
        # second element of quadruple
        second = first.next
 
        while (second != None and
               fourth != None and
               second != fourth and
          fourth.next != second):
 
            reqsum = x - (first.data +
                         second.data)
 
            # Points to the 3rd element
            # of quadruple
            third = second.next
 
            # Points to the tail of the DLL
            temp = fourth
 
            while (third != None and temp != None and
                   third != temp and temp.next != third):
 
                # Store the current sum
                twosum = third.data + temp.data
 
                # If the sum is equal,
                # then print quadruple
                if (twosum == reqsum):
 
                    print("(" + str(first.data) +
                         ", " + str(second.data) +
                         ", " + str(third.data) +
                         ", " + str(temp.data) + ")")
                    third = third.next
                    temp = temp.prev
 
                # If twosum is less than
                # the reqsum then move the
                # third pointer to the next
                elif (twosum < reqsum):
                    third = third.next
                     
                # Otherwise move the fourth
                # pointer to the previous
                # of the fourth pointer
                else:
                    temp = temp.prev
 
            # Move to the next of
            # the second pointer
            second = second.next
 
        # Move to the next of
        # the first pointer
        first = first.next
 
# Driver Code
if __name__ == '__main__':
     
    head = None
    head = insert(head, 2)
    head = insert(head, 1)
    head = insert(head, 0)
    head = insert(head, 0)
    head = insert(head, -1)
    head = insert(head, -2)
    X = 0
     
    PrintFourSum(head, X)
     
# This code is contributed by mohit kumar 29

C#

// C# program for the above approach
using System;
 
public class GFG {
 
    // structure of node of
    // doubly linked list
public    class Node {
    public    int data;
    public    Node next, prev;
    };
 
    // A utility function to insert
    // a new node at the beginning
    // of the doubly linked list
    static Node insert(Node head, int data) {
 
        // Allocate the node
        Node temp = new Node();
 
        // Fill in the data value
        temp.data = data;
        temp.next = temp.prev = null;
        if (head == null)
            (head) = temp;
        else {
            temp.next = head;
            (head).prev = temp;
            (head) = temp;
        }
        return temp;
    }
 
    // Function to print the quadruples
    // having sum equal to x
    static void PrintFourSum(Node head, int x) {
 
        // First pointer to the head node
        Node first = head;
 
        // Pointer to point to the second
        // node for the required sum
        Node second = head;
 
        // Pointer to point to the third
        // node for the required sum
        Node third = head;
 
        // Fourth points to the last node
        Node fourth = head;
 
        // Update the fourth pointer to
        // the end of the DLL
        while (fourth.next != null) {
            fourth = fourth.next;
        }
 
        // Node to point to the fourth node
        // of the required sum
        Node temp;
        while (first != null && fourth != null && first != fourth && fourth.next != first) {
 
            // Point the second node to the
            // second element of quadruple
            second = first.next;
 
            while (second != null && fourth != null && second != fourth && fourth.next != second) {
 
                int reqsum = x - (first.data + second.data);
 
                // Points to the 3rd element
                // of quadruple
                third = second.next;
 
                // Points to the tail of the DLL
                temp = fourth;
 
                while (third != null && temp != null && third != temp && temp.next != third) {
 
                    // Store the current sum
                    int twosum = third.data + temp.data;
 
                    // If the sum is equal,
                    // then print quadruple
                    if (twosum == reqsum) {
 
                        Console.WriteLine(
                                "(" + first.data + ", " + second.data + ", " + third.data + ", " + temp.data + ")");
 
                        third = third.next;
                        temp = temp.prev;
                    }
 
                    // If twosum is less than
                    // the reqsum then move the
                    // third pointer to the next
                    else if (twosum < reqsum) {
                        third = third.next;
                    }
 
                    // Otherwise move the fourth
                    // pointer to the previous
                    // of the fourth pointer
                    else {
                        temp = temp.prev;
                    }
                }
 
                // Move to the next of
                // the second pointer
                second = second.next;
            }
 
            // Move to the next of
            // the first pointer
            first = first.next;
        }
    }
 
    // Driver Code
    public static void Main(String []args) {
 
        Node head = null;
        head = insert(head, 2);
        head = insert(head, 1);
        head = insert(head, 0);
        head = insert(head, 0);
        head = insert(head, -1);
        head = insert(head, -2);
        int x = 0;
 
        PrintFourSum(head, x);
    }
}
 
// This code is contributed by gauravrajput1

Javascript

<script>
 
// Javascript program for the above approach
 
// Structure of node of a doubly
// linked list
class Node {
 
    constructor()
    {
        this.data = 0;
        this.next = null;
        this.prev = null;
    }
};
 
// Function to insert a new node at
// the beginning of the doubly linked
// list
function insert(head, data)
{
    // Allocate the node
    var temp = new Node();
 
    // Fill in the data value
    temp.data = data;
    temp.next = temp.prev = null;
 
    if ((head) == null)
        (head) = temp;
    else {
        temp.next = head;
        (head).prev = temp;
        (head) = temp;
    }
    return head;
}
 
// Function to print the quadruples
// having sum equal to x
function PrintFourSum(head, x)
{
    // First pointer to the head node
    var first = head;
 
    // Pointer to point to the second
    // node for the required sum
    var second;
 
    // Pointer to point to the third
    // node for the required sum
    var third;
 
    // Fourth points to the last node
    var fourth = head;
 
    // Update the fourth pointer to
    // the end of the DLL
    while (fourth.next != null) {
        fourth = fourth.next;
    }
 
    // Node to point to the fourth node
    // of the required sum
    var temp;
 
    while (first != null
           && fourth != null
           && first != fourth
           && fourth.next != first) {
 
        // Point the second node to the
        // second element of quadruple
        second = first.next;
 
        while (second != null
               && fourth != null
               && second != fourth
               && fourth.next != second) {
 
            var reqsum = x - (first.data
                              + second.data);
 
            // Points to the 3rd element
            // of quadruple
            third = second.next;
 
            // Points to the tail of the DLL
            temp = fourth;
 
            while (third != null && temp != null
                   && third != temp
                   && temp.next != third) {
 
                // Store the current sum
                var twosum = third.data
                             + temp.data;
 
                // If the sum is equal,
                // then print quadruple
                if (twosum == reqsum) {
 
                    document.write( "(" + first.data
                         + ", "
                         + second.data
                         + ", "
                         + third.data
                         + ", "
                         + temp.data
                         + ")<br>");
 
                    third = third.next;
                    temp = temp.prev;
                }
 
                // If twosum is less than
                // the reqsum then move the
                // third pointer to the next
                else if (twosum < reqsum) {
                    third = third.next;
                }
 
                // Otherwise move the fourth
                // pointer to the previous
                // of the fourth pointer
                else {
                    temp = temp.prev;
                }
            }
 
            // Move to the next of
            // the second pointer
            second = second.next;
        }
 
        // Move to the next of
        // the first pointer
        first = first.next;
    }
}
 
// Driver Code
var head = null;
head = insert(head, 2);
head = insert(head, 1);
head = insert(head, 0);
head = insert(head, 0);
head = insert(head, -1);
head = insert(head, -2);
var X = 0;
PrintFourSum(head, X);
 
// This code is contributed by rrrtnx.
</script>
Producción

(-2, -1, 1, 2)
(-2, 0, 0, 2)
(-1, 0, 0, 1)

Complejidad de Tiempo: O(N 3 )
Espacio Auxiliar: O(1)

Publicación traducida automáticamente

Artículo escrito por geekyss 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 *