Dada una lista enlazada simple. La tarea es encontrar la suma de los Nodes de la lista enlazada dada.
Ejemplos:
Input: 7->6->8->4->1 Output: 26 Sum of nodes: 7 + 6 + 8 + 4 + 1 = 26 Input: 1->7->3->9->11->5 Output: 36
Solución recursiva:
- Llame a una función pasando el encabezado y la variable para almacenar la suma.
- Luego llame recursivamente a la función pasando el siguiente Node actual y la variable de suma.
- Agregue el valor del Node actual a la suma.
- Luego llame recursivamente a la función pasando el siguiente Node actual y la variable de suma.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the sum of // nodes of the Linked List #include <bits/stdc++.h> using namespace std; /* A Linked list node */ struct Node { int data; struct Node* next; }; // function to insert a node at the // beginning of the linked list void push(struct Node** head_ref, int new_data) { /* allocate node */ struct Node* new_node = new Node; /* put in the data */ new_node->data = new_data; /* link the old list to the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } // function to recursively find the sum of // nodes of the given linked list void sumOfNodes(struct Node* head, int* sum) { // if head = NULL if (!head) return; // recursively traverse the remaining nodes sumOfNodes(head->next, sum); // accumulate sum *sum = *sum + head->data; } // utility function to find the sum of nodes int sumOfNodesUtil(struct Node* head) { int sum = 0; // find the sum of nodes sumOfNodes(head, &sum); // required sum return sum; } // Driver program to test above int main() { struct Node* head = NULL; // create linked list 7->6->8->4->1 push(&head, 7); push(&head, 6); push(&head, 8); push(&head, 4); push(&head, 1); cout << "Sum of nodes = " << sumOfNodesUtil(head); return 0; }
Java
// Java implementation to find the sum of // nodes of the Linked List class GFG { static int sum=0; // A Linked list node / static class Node { int data; Node next; } // function to insert a node at the // beginning of the linked list static Node push( Node head_ref, int new_data) { // allocate node / Node new_node = new Node(); // put in the data / new_node.data = new_data; // link the old list to the new node / new_node.next = (head_ref); // move the head to point to the new node / (head_ref) = new_node; return head_ref; } // function to recursively find the sum of // nodes of the given linked list static void sumOfNodes( Node head) { // if head = null if (head == null) return; // recursively traverse the remaining nodes sumOfNodes(head.next); // accumulate sum sum = sum + head.data; } // utility function to find the sum of nodes static int sumOfNodesUtil( Node head) { sum = 0; // find the sum of nodes sumOfNodes(head); // required sum return sum; } // Driver program to test above public static void main(String args[]) { Node head = null; // create linked list 7.6.8.4.1 head = push(head, 7); head = push(head, 6); head = push(head, 8); head = push(head, 4); head = push(head, 1); System.out.println( "Sum of nodes = " + sumOfNodesUtil(head)); } } // This code is contributed by Arnab Kundu
Python3
# Python3 implementation to find the sum of # nodes of the Linked List import math # class for a Sum class Sum: tsum = None # A Linked list node class Node: def __init__(self,data): self.data = data self.next = None # function to insert a node at the # beginning of the linked list def push(head, data): if not head: return Node(data) # put in the data # and allocate node new_node = Node(data) # link the old list to the new node new_node.next = head # move the head to point # to the new node head = new_node return head # function to recursively find # the sum of nodes of the given # linked list def sumOfNode(head, S): # if head = NULL if not head: return # recursively traverse the # remaining nodes sumOfNode(head.next, S) # accumulate sum S.tsum += head.data # utility function to find # the sum of nodes def sumOfNodesUtil(head): S = Sum() S.tsum = 0 # find the sum of nodes sumOfNode(head, S) # required sum return S.tsum # Driver Code if __name__=='__main__': head = None # create linked list 7->6->8->4->1 head = push(head, 7) head = push(head, 6) head = push(head, 8) head = push(head, 4) head = push(head, 1) print("Sum of Nodes = {}" . format(sumOfNodesUtil(head))) # This code is contributed # by Vikash Kumar 37
C#
// C# implementation to find the sum of // nodes of the Linked List using System; class GFG { public static int sum = 0; // A Linked list node / public class Node { public int data; public Node next; } // function to insert a node at the // beginning of the linked list static Node push(Node head_ref, int new_data) { // allocate node / Node new_node = new Node(); // put in the data / new_node.data = new_data; // link the old list to the new node / new_node.next = (head_ref); // move the head to point to the new node / (head_ref) = new_node; return head_ref; } // function to recursively find the sum of // nodes of the given linked list static void sumOfNodes(Node head) { // if head = null if (head == null) return; // recursively traverse the remaining nodes sumOfNodes(head.next); // accumulate sum sum = sum + head.data; } // utility function to find the sum of nodes static int sumOfNodesUtil(Node head) { sum = 0; // find the sum of nodes sumOfNodes(head); // required sum return sum; } // Driver program to test above public static void Main(String[] args) { Node head = null; // create linked list 7.6.8.4.1 head = push(head, 7); head = push(head, 6); head = push(head, 8); head = push(head, 4); head = push(head, 1); Console.WriteLine("Sum of nodes = " + sumOfNodesUtil(head)); } } // This code is contributed by Rajput-Ji
Javascript
<script> // JavaScript implementation to find the sum of // nodes of the Linked List var sum = 0; // A Linked list node / class Node { constructor(val) { this.data = val; this.next = null; } } // function to insert a node at the // beginning of the linked list function push(head_ref , new_data) { // allocate node / var new_node = new Node(); // put in the data / new_node.data = new_data; // link the old list to the new node / new_node.next = (head_ref); // move the head to point to the new node / (head_ref) = new_node; return head_ref; } // function to recursively find the sum of // nodes of the given linked list function sumOfNodes(head) { // if head = null if (head == null) return; // recursively traverse the remaining nodes sumOfNodes(head.next); // accumulate sum sum = sum + head.data; } // utility function to find the sum of nodes function sumOfNodesUtil(head) { sum = 0; // find the sum of nodes sumOfNodes(head); // required sum return sum; } // Driver program to test above var head = null; // create linked list 7.6.8.4.1 head = push(head, 7); head = push(head, 6); head = push(head, 8); head = push(head, 4); head = push(head, 1); document.write("Sum of nodes = " + sumOfNodesUtil(head)); // This code contributed by umadevi9616 </script>
Producción:
Sum of nodes = 26
Complejidad de tiempo: O(N), N es el número de Nodes en una lista enlazada.
Espacio auxiliar: O(N), solo si se considera el tamaño de la pila durante las llamadas recursivas.
Solución iterativa:
- Inicialice un puntero ptr con el encabezado de la lista enlazada y una variable de suma con 0.
- Comience a recorrer la lista vinculada utilizando un bucle hasta que se atraviesen todos los Nodes.
- Agregue el valor del Node actual a la suma, es decir , suma += ptr -> datos .
- Incremente el puntero al siguiente Node de la lista enlazada, es decir , ptr = ptr ->next .
- Devolver la suma .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the sum of // nodes of the Linked List #include <bits/stdc++.h> using namespace std; /* A Linked list node */ struct Node { int data; struct Node* next; }; // function to insert a node at the // beginning of the linked list void push(struct Node** head_ref, int new_data) { /* allocate node */ struct Node* new_node = new Node; /* put in the data */ new_node->data = new_data; /* link the old list to the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } // function to find the sum of // nodes of the given linked list int sumOfNodes(struct Node* head) { struct Node* ptr = head; int sum = 0; while (ptr != NULL) { sum += ptr->data; ptr = ptr->next; } return sum; } // Driver program to test above int main() { struct Node* head = NULL; // create linked list 7->6->8->4->1 push(&head, 7); push(&head, 6); push(&head, 8); push(&head, 4); push(&head, 1); cout << "Sum of nodes = " << sumOfNodes(head); return 0; }
Java
// Java implementation to find the sum of // nodes of the Linked List class GFG { static Node head; /* A Linked list node */ static class Node { int data; Node next; }; // function to insert a node at the // beginning of the linked list // Inserting node at the beginning static Node push(Node head_ref, int new_data) { /* allocate node */ Node new_node = new Node(); /* put in the data */ new_node.data = new_data; /* link the old list to the new node */ new_node.next = head_ref; /* move the head to point to the new node */ head_ref = new_node; return head=head_ref; } // function to find the sum of // nodes of the given linked list static int sumOfNodes( Node head) { Node ptr = head; int sum = 0; while (ptr != null) { sum += ptr.data; ptr = ptr.next; } return sum; } // Driver code public static void main(String[] args) { // create linked list 7.6.8.4.1 push(head, 7); push(head, 6); push(head, 8); push(head, 4); push(head, 1); System.out.println("Sum of nodes = " + sumOfNodes(head)); } } /* This code is contributed by PrinciRaj1992 */
Python3
# Python3 implementation to find the # sum of nodes of the Linked List import math # A Linked list node class Node: def __init__(self, data): self.data = data self.next = None # function to insert a node at the # beginning of the linked list def push(head_ref, new_data): # allocate node new_node = Node(new_data) # put in the data new_node.data = new_data # link the old list to the new node new_node.next = head_ref # move the head to po to the new node head_ref = new_node return head_ref # function to find the sum of # nodes of the given linked list def sumOfNodes(head): ptr = head sum = 0 while (ptr != None): sum = sum + ptr.data ptr = ptr.next return sum # Driver Code if __name__=='__main__': head = None # create linked list 7.6.8.4.1 head = push(head, 7) head = push(head, 6) head = push(head, 8) head = push(head, 4) head = push(head, 1) print("Sum of nodes =", sumOfNodes(head)) # This code is contributed by Srathore
C#
// C# implementation to find the sum of // nodes of the Linked List using System; class GFG { static Node head; /* A Linked list node */ public class Node { public int data; public Node next; }; // function to insert a node at the // beginning of the linked list // Inserting node at the beginning static Node push(Node head_ref, int new_data) { /* allocate node */ Node new_node = new Node(); /* put in the data */ new_node.data = new_data; /* link the old list to the new node */ new_node.next = head_ref; /* move the head to point to the new node */ head_ref = new_node; return head=head_ref; } // function to find the sum of // nodes of the given linked list static int sumOfNodes( Node head) { Node ptr = head; int sum = 0; while (ptr != null) { sum += ptr.data; ptr = ptr.next; } return sum; } // Driver code public static void Main(String[] args) { // create linked list 7.6.8.4.1 push(head, 7); push(head, 6); push(head, 8); push(head, 4); push(head, 1); Console.WriteLine("Sum of nodes = " + sumOfNodes(head)); } } // This code is contributed by 29AjayKumar
Javascript
<script> // javascript implementation to find the sum of // nodes of the Linked List var head; /* A Linked list node */ class Node { constructor() { this.data = 0; this.next = null; } } // function to insert a node at the // beginning of the linked list // Inserting node at the beginning function push(head_ref , new_data) { /* allocate node */ var new_node = new Node(); /* put in the data */ new_node.data = new_data; /* link the old list to the new node */ new_node.next = head_ref; /* move the head to point to the new node */ head_ref = new_node; return head = head_ref; } // function to find the sum of // nodes of the given linked list function sumOfNodes(head) { var ptr = head; var sum = 0; while (ptr != null) { sum += ptr.data; ptr = ptr.next; } return sum; } // Driver code // create linked list 7.6.8.4.1 push(head, 7); push(head, 6); push(head, 8); push(head, 4); push(head, 1); document.write("Sum of nodes = " + sumOfNodes(head)); // This code contributed by aashish1995 </script>
Producción:
Sum of nodes = 26
Complejidad de tiempo: O(N), N es el número de Nodes en una lista enlazada.
Espacio Auxiliar: O(1)