Dada una lista enlazada de un número par de Nodes, la tarea es generar una nueva lista enlazada que contenga la diferencia máxima de cuadrados de valores de Nodes en orden decreciente al incluir cada Node en un solo par.
Ejemplos:
Entrada: 1 -> 6 -> 4 -> 3 -> 5 ->2
Salida: 35 -> 21 -> 7
Explicación:
La diferencia entre cuadrados de 6 y 1 forma el primer Node con valor 35.
La diferencia entre cuadrados de 5 y 2 forma el segundo Node con valor 21.
La diferencia entre los cuadrados de 4 y 3 forma el tercer Node con valor 7.
Por lo tanto, la LL formada es 35 -> 21 -> 7.Entrada: 2 -> 4 -> 5 -> 3 -> 7 -> 8 -> 9 -> 10
Salida: 96 -> 72 -> 48 -> 10
Explicación:
La diferencia entre los cuadrados de 10 y 2 forma el primer Node con valor 96.
La diferencia entre cuadrados de 9 y 3 forma el segundo Node con valor 72.
La diferencia entre cuadrados de 8 y 4 forma el tercer Node con valor 48.
La diferencia entre cuadrados de 7 y 5 forma el cuarto Node con valor 10.
Por tanto, la LL formada es 96 -> 72 -> 48 -> 10.
Enfoque: El enfoque es encontrar el valor máximo de un Node y siempre hacer la diferencia entre el valor de Node más grande y el más pequeño. Así que cree un deque e inserte todos los valores de los Nodes en él, y ordene el deque . Ahora, acceda a los valores más grandes y más pequeños de ambos extremos. A continuación se muestran los pasos:
- Cree una deque e inserte todos los valores en la deque.
- Ordene el deque para obtener el valor de Node más grande y el valor de Node más pequeño en tiempo constante.
- Cree otra lista enlazada que tenga la diferencia de valores de los cuadrados de los valores más grandes y más pequeños de la parte posterior y frontal del deque, respectivamente.
- Después de cada iteración, saque tanto el valor más pequeño como el más grande del deque.
- Después de los pasos anteriores, imprima los Nodes de la nueva Lista Enlazada formada.
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; // Linked list node struct Node { int data; struct Node* next; }; // Function to push into Linked List void push(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; new_node->next = (*head_ref); // Move the head to point // to the new node (*head_ref) = new_node; } // Function to print the Linked List void print(struct Node* head) { Node* curr = head; // Iterate until curr is NULL while (curr) { // Print the data cout << curr->data << " "; // Move to next curr = curr->next; } } // Function to create a new Node of // the Linked List struct Node* newNode(int x) { struct Node* temp = (struct Node*)malloc( sizeof(struct Node)); temp->data = x; temp->next = NULL; // Return the node created return temp; } // Function used to re-order list struct Node* reorder(Node* head) { // Stores the node of LL deque<int> v; Node* curr = head; // Traverse the LL while (curr) { v.push_back(curr->data); curr = curr->next; } // Sort the deque sort(v.begin(), v.end()); // Node head1 stores the // head of the new Linked List Node* head1 = NULL; Node* prev = NULL; // Size of new LL int x = v.size() / 2; // Loop to make new LL while (x--) { int a = v.front(); int b = v.back(); // Difference of squares of // largest and smallest value int ans = pow(b, 2) - pow(a, 2); // Create node with value ans struct Node* temp = newNode(ans); if (head1 == NULL) { head1 = temp; prev = temp; } // Otherwise, update prev else { prev->next = temp; prev = temp; } // Pop the front and back node v.pop_back(); v.pop_front(); } // Return head of the new LL return head1; } // Driver Code int main() { struct Node* head = NULL; // Given Linked list push(&head, 6); push(&head, 5); push(&head, 4); push(&head, 3); push(&head, 2); push(&head, 1); // Function Call Node* temp = reorder(head); // Print the new LL formed print(temp); return 0; }
Java
// Java program for the // above approach import java.util.*; class GFG{ // Linked list node static class Node { int data; Node next; }; static Node head ; // Function to push // into Linked List static void push(int new_data) { // Allocate node Node new_node = new Node(); // Put in the data new_node.data = new_data; new_node.next = head; // Move the head to point // to the new node head = new_node; } // Function to print the // Linked List static void print(Node head) { Node curr = head; // Iterate until curr // is null while (curr != null) { // Print the data System.out.print(curr.data + " "); // Move to next curr = curr.next; } } // Function to create a // new Node of the Linked List static Node newNode(int x) { Node temp = new Node(); temp.data = x; temp.next = null; // Return the node // created return temp; } // Function used to re-order // list static Node reorder(Node head) { // Stores the node of LL Deque<Integer> v = new LinkedList<>(); Node curr = head; // Traverse the LL while (curr != null) { v.add(curr.data); curr = curr.next; } // Sort the deque // Collections.sort(v); // Node head1 stores the // head of the new Linked // List Node head1 = null; Node prev = null; // Size of new LL int x = v.size() / 2; // Loop to make new LL while ((x--) > 0) { int a = v.peek(); int b = v.getLast(); // Difference of squares of // largest and smallest value int ans = (int)(Math.pow(b, 2) - Math.pow(a, 2)); // Create node with value ans Node temp = newNode(ans); if (head1 == null) { head1 = temp; prev = temp; } // Otherwise, update prev else { prev.next = temp; prev = temp; } // Pop the front and // back node v.removeFirst(); v.removeLast(); } // Return head of the // new LL return head1; } // Driver Code public static void main(String[] args) { head = null; // Given Linked list push(6); push(5); push(4); push(3); push(2); push(1); // Function Call Node temp = reorder(head); // Print the new // LL formed print(temp); } } // This code is contributed by Amit Katiyar
Python3
# Python3 program for the # above approach from collections import deque # Linked list node class Node: def __init__(self, x): self.data = x self.next = None # Function to push into Linked List # Function to push into Linked List def push(head_ref, new_data): new_node = Node(new_data) new_node.next = head_ref head_ref = new_node return head_ref # Function to print the Linked List def printt(head): curr = head # Iterate until curr # is None while (curr): # Print the data print(curr.data, end = " ") # Move to next curr = curr.next # Function used to re-order list # Function used to re-order list def reorder(head): # Stores the node of LL arr = [] curr = head while curr: arr.append(curr.data) curr = curr.next arr = sorted(arr) # Sort the deque v = deque() for i in arr: v.append(i) # Node head1 stores the # head of the new Linked List head1 = None prev = None x = len(arr) // 2 while x: a = v.popleft() b = v.pop() # Difference of squares of # largest and smallest value ans = pow(b, 2) - pow(a, 2) temp = Node(ans) if head1 == None: head1 = temp prev = temp else: prev.next = temp prev = temp x -= 1 # Return head of the new LL return head1 # Driver Code if __name__ == '__main__': head = None # Given Linked list head = push(head, 6) head = push(head, 5) head = push(head, 4) head = push(head, 3) head = push(head, 2) head = push(head, 1) # Function Call temp = reorder(head) # Print the new LL formed printt(temp) # This code is contributed by Mohit kumar 29
C#
// C# program for the // above approach using System; using System.Collections.Generic; class GFG{ // Linked list node public class Node { public int data; public Node next; }; static Node head ; // Function to push // into Linked List static void push(int new_data) { // Allocate node Node new_node = new Node(); // Put in the data new_node.data = new_data; new_node.next = head; // Move the head to point // to the new node head = new_node; } // Function to print the // Linked List static void print(Node head) { Node curr = head; // Iterate until curr // is null while (curr != null) { // Print the data Console.Write(curr.data + " "); // Move to next curr = curr.next; } } // Function to create a // new Node of the Linked List static Node newNode(int x) { Node temp = new Node(); temp.data = x; temp.next = null; // Return the node // created return temp; } // Function used to re-order // list static Node reorder(Node head) { // Stores the node of LL List<int> v = new List<int>(); Node curr = head; // Traverse the LL while (curr != null) { v.Add(curr.data); curr = curr.next; } // Sort the deque // Collections.sort(v); // Node head1 stores the // head of the new Linked // List Node head1 = null; Node prev = null; // Size of new LL int x = v.Count / 2; // Loop to make new LL while ((x--) > 0) { int a = v[0]; int b = v[v.Count-1]; // Difference of squares of // largest and smallest value int ans = (int)(Math.Pow(b, 2) - Math.Pow(a, 2)); // Create node with value ans Node temp = newNode(ans); if (head1 == null) { head1 = temp; prev = temp; } // Otherwise, update prev else { prev.next = temp; prev = temp; } // Pop the front and // back node v.RemoveAt(0); v.RemoveAt(v.Count - 1); } // Return head of the // new LL return head1; } // Driver Code public static void Main(String[] args) { head = null; // Given Linked list push(6); push(5); push(4); push(3); push(2); push(1); // Function Call Node temp = reorder(head); // Print the new // LL formed print(temp); } } // This code is contributed by gauravrajput1
Javascript
<script> // javascript program for the // above approach // Linked list node class Node { constructor(val) { this.data = val; this.next = null; } } var head; // Function to push // into Linked List function push(new_data) { // Allocate node var new_node = new Node(); // Put in the data new_node.data = new_data; new_node.next = head; // Move the head to point // to the new node head = new_node; } // Function to print the // Linked List function print(head) { var curr = head; // Iterate until curr // is null while (curr != null) { // Print the data document.write(curr.data + " "); // Move to next curr = curr.next; } } // Function to create a // new Node of the Linked List function newNode(x) { var temp = new Node(); temp.data = x; temp.next = null; // Return the node // created return temp; } // Function used to re-order // list function reorder(head) { // Stores the node of LL var v = []; var curr = head; // Traverse the LL while (curr != null) { v.push(curr.data); curr = curr.next; } // Sort the deque // Collections.sort(v); // Node head1 stores the // head of the new Linked // List var head1 = null; var prev = null; // Size of new LL var x = v.length / 2; // Loop to make new LL while ((x--) > 0) { var a = v[0]; var b = v[v.length-1]; // Difference of squares of // largest and smallest value var ans = parseInt( (Math.pow(b, 2) - Math.pow(a, 2))); // Create node with value ans var temp = newNode(ans); if (head1 == null) { head1 = temp; prev = temp; } // Otherwise, update prev else { prev.next = temp; prev = temp; } // Pop the front and // back node v.pop(); v.shift(); } // Return head of the // new LL return head1; } // Driver Code head = null; // Given Linked list push(6); push(5); push(4); push(3); push(2); push(1); // Function Call var temp = reorder(head); // Print the new // LL formed print(temp); // This code is contributed by todaysgaurav </script>
35 21 7
Complejidad de tiempo: O(N*log N)
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por kothawade29 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA