Dado el encabezado de una lista enlazada de enteros y un entero k, su tarea es modificar la lista enlazada de la siguiente manera:
- Considere los Nodes en grupos de tamaño k. En cada grupo, reemplace el valor del primer Node con la suma del grupo.
- Además, elimine los elementos del grupo excepto el primer Node.
- Durante el recorrido, si los Nodes restantes en la lista enlazada son menores que k, también haga lo anterior considerando los Nodes restantes.
Ejemplos:
Entrada: N = 6, K = 2
1->2->3->4->5->6
Salida: 3 7 11
Hemos denotado la agrupación de k elementos por(). Los elementos dentro de() se suman.
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> nulo
(1 -> 2) -> 3 -> 4 -> 5 -> 6 -> nulo
(3) -> 3 -> 4 – > 5 -> 6 -> nulo
3 -> (3 -> 4) -> 5 -> 6 -> nulo
3 -> (7) -> 5 -> 6 -> nulo
3 -> 7 -> (5 – > 6) -> nulo
3 -> 7 -> (11) -> nulo
3 -> 7 -> 11 -> nulo
Enfoque: Inserte los Nodes dados en la lista Vinculada. El enfoque de la inserción se ha discutido en esta publicación. Una vez insertados los Nodes, itere desde el principio de la lista. Marque el primer Node como Node temporal . Iterar para los siguientes k-1 Nodes y resumir los Nodes en sumavariable. Si el número de Nodes es inferior a K, reemplace los datos del Node temporal con suma y apunte la temperatura a NULL. Si hay un grupo con K Nodes, reemplace los datos de temp con sum y mueva temp al Node que está justo después de K Nodes. Continúe con la operación anterior hasta que la temperatura apunte a NULL. Una vez que temp llega al final, significa que todos los grupos de tamaño K han sido recorridos y el Node ha sido reemplazado con la suma de Nodes de tamaño K. Una vez realizada la operación de reemplazo, se puede imprimir la lista enlazada así formada. El método de impresión de la lista enlazada se ha discutido en esta publicación.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for // SP - K Sum #include <iostream> using namespace std; // structure for linked list struct Node { long long data; Node* next; }; // allocated new node Node* newNode(int key) { Node* temp = new Node; temp->data = key; temp->next = NULL; return temp; } // function to insert node in a Linked List Node* insertNode(Node* head, int key) { if (head == NULL) head = newNode(key); else head->next = insertNode(head->next, key); return head; } // traverse the node // to print it void print(Node* head) { // traverse the linked list while (head) { cout << head->data << " "; head = head->next; } cout << endl; } // function to perform the following operation void KSum(Node* head, int k) { // initially pointing to start Node* temp = head; // iterate till end while (temp) { // dummy variable to store k long long count = k; // summation of nodes long long sum = 0; // currently at node from // which iteration is done Node* curr = temp; // till k nodes are visited and // last node is not visited while (count-- && curr) { // add to sum the node data sum = sum + curr->data; // move to the next node curr = curr->next; } // change pointer's data of temp to sum temp->data = sum; // move temp to next pointer temp->next = curr; // move temp to the next pointer temp = temp->next; } } // Driver Code int main() { Node* head = NULL; // inserts nodes in the linked list head = insertNode(head, 1); head = insertNode(head, 2); head = insertNode(head, 3); head = insertNode(head, 4); head = insertNode(head, 5); head = insertNode(head, 6); int k = 2; // Function call to perform the // given operations KSum(head, k); // print the linked list print(head); return 0; }
Java
// Java program for // SP - K Sum import java.io.*; import java.util.*; // structure for linked list class Node { int data; Node next; Node(int key) { data = key; next = null; } } class GFG { // allocated new node static Node head; // function to insert node // in a Linked List public static Node insertNode(Node head, int key) { if (head == null) head = new Node(key); else head.next = insertNode(head.next, key); return head; } // traverse the node // to print it public static void print(Node head) { // traverse the linked list while (head != null) { System.out.print(head.data + " "); head = head.next; } System.out.println(); } // function to perform // the following operation public static void KSum(Node head, int k) { // initially pointing // to start Node temp = head; // iterate till end while (temp != null) { // dummy variable // to store k int count = k; // summation of nodes int sum = 0; // currently at node from // which iteration is done Node curr = temp; // till k nodes are visited and // last node is not visited while (count > 0 && curr != null) { // add to sum the node data sum = sum + curr.data; // move to the next node curr = curr.next; count--; } // change pointer's data // of temp to sum temp.data = sum; // move temp to // next pointer temp.next = curr; // move temp to // the next pointer temp = temp.next; } //return temp; } // Driver Code public static void main(String args[]) { head = null; // inserts nodes in // the linked list head = insertNode(head, 1); head = insertNode(head, 2); head = insertNode(head, 3); head = insertNode(head, 4); head = insertNode(head, 5); head = insertNode(head, 6); int k = 2; // Function call to perform // the given operations KSum(head, k); // print the linked list print(head); } }
Python3
# Python program for # SP - K Sum # structure for linked list class Node: def __init__(self, key): self.data = key self.next = None # function to insert node in a Linked List def insertNode(head: Node, key: int) -> Node: if head is None: head = Node(key) else: head.next = insertNode(head.next, key) return head # traverse the node # to print it def Print(head: Node): # traverse the linked list while head: print(head.data, end = " ") head = head.next print() # function to perform the following operation def KSum(head: Node, k: int): # initially pointing to start temp = head # iterate till end while temp: # dummy variable to store k count = k # summation of nodes sum = 0 # currently at node from # which iteration is done curr = temp # till k nodes are visited and # last node is not visited while count and curr: # add to sum the node data sum = sum + curr.data # move to the next node curr = curr.next count -= 1 # change pointer's data of temp to sum temp.data = sum # move temp to next pointer temp.next = curr # move temp to the next pointer temp = temp.next # Driver Code if __name__ == "__main__": head = None # inserts nodes in the linked list head = insertNode(head, 1) head = insertNode(head, 2) head = insertNode(head, 3) head = insertNode(head, 4) head = insertNode(head, 5) head = insertNode(head, 6) k = 2 # Function call to perform the # given operations KSum(head, k) # print the linked list Print(head) # This code is contributed by # sanjeev2552
C#
// C# program for SP - K Sum using System; // structure for linked list public class Node { public int data; public Node next; public Node(int key) { data = key; next = null; } } public class GFG { // allocated new node static Node head; // function to insert node // in a Linked List public static Node insertNode(Node head, int key) { if (head == null) head = new Node(key); else head.next = insertNode(head.next, key); return head; } // traverse the node // to print it public static void print(Node head) { // traverse the linked list while (head != null) { Console.Write(head.data + " "); head = head.next; } Console.WriteLine(); } // function to perform // the following operation public static void KSum(Node head, int k) { // initially pointing // to start Node temp = head; // iterate till end while (temp != null) { // dummy variable // to store k int count = k; // summation of nodes int sum = 0; // currently at node from // which iteration is done Node curr = temp; // till k nodes are visited and // last node is not visited while (count > 0 && curr != null) { // add to sum the node data sum = sum + curr.data; // move to the next node curr = curr.next; count--; } // change pointer's data // of temp to sum temp.data = sum; // move temp to // next pointer temp.next = curr; // move temp to // the next pointer temp = temp.next; } // return temp; } // Driver Code public static void Main() { head = null; // inserts nodes in // the linked list head = insertNode(head, 1); head = insertNode(head, 2); head = insertNode(head, 3); head = insertNode(head, 4); head = insertNode(head, 5); head = insertNode(head, 6); int k = 2; // Function call to perform // the given operations KSum(head, k); // print the linked list print(head); } } /* This code contributed by PrinciRaj1992 */
Javascript
<script> // JavaScript program for SP - K Sum // structure for linked list class Node { constructor(key) { this.data = key; this.next = null; } } // allocated new node var head = null; // function to insert node // in a Linked List function insertNode(head, key) { if (head == null) head = new Node(key); else head.next = insertNode(head.next, key); return head; } // traverse the node // to print it function print(head) { // traverse the linked list while (head != null) { document.write(head.data + " "); head = head.next; } document.write("<br>"); } // function to perform // the following operation function KSum(head, k) { // initially pointing // to start var temp = head; // iterate till end while (temp != null) { // dummy variable // to store k var count = k; // summation of nodes var sum = 0; // currently at node from // which iteration is done var curr = temp; // till k nodes are visited and // last node is not visited while (count > 0 && curr != null) { // add to sum the node data sum = sum + curr.data; // move to the next node curr = curr.next; count--; } // change pointer's data // of temp to sum temp.data = sum; // move temp to // next pointer temp.next = curr; // move temp to // the next pointer temp = temp.next; } // return temp; } // Driver Code head = null; // inserts nodes in // the linked list head = insertNode(head, 1); head = insertNode(head, 2); head = insertNode(head, 3); head = insertNode(head, 4); head = insertNode(head, 5); head = insertNode(head, 6); var k = 2; // Function call to perform // the given operations KSum(head, k); // print the linked list print(head); // This code is contributed by rdtank. </script>
Producción:
3 7 11
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