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)