给定一个链表和一个数字 N .找出最后一个的总和 N 链接列表的节点。 限制条件： 0 <= N <=链表中的节点数。
null
例如：
Input : 10->6->8->4->12, n = 2Output : 16Sum of last two nodes:12 + 4 = 16Input : 15->7->9->5->16->14, n = 4Output : 44
方法1：（使用系统调用堆栈的递归方法） 递归地遍历链表直到最后。现在，在函数调用返回的过程中，将最后一个 N 节点。总和可以累加在某个变量中，该变量通过引用传递给函数或某个全局变量。
C++
// C++ implementation to find the sum of // last 'n' 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 last // 'n' nodes of the given linked list void sumOfLastN_Nodes( struct Node* head, int * n, int * sum) { // if head = NULL if (!head) return ; // recursively traverse the remaining nodes sumOfLastN_Nodes(head->next, n, sum); // if node count 'n' is greater than 0 if (*n > 0) { // accumulate sum *sum = *sum + head->data; // reduce node count 'n' by 1 --*n; } } // utility function to find the sum of last 'n' nodes int sumOfLastN_NodesUtil( struct Node* head, int n) { // if n == 0 if (n <= 0) return 0; int sum = 0; // find the sum of last 'n' nodes sumOfLastN_Nodes(head, &n, &sum); // required sum return sum; } // Driver program to test above int main() { struct Node* head = NULL; // create linked list 10->6->8->4->12 push(&head, 12); push(&head, 4); push(&head, 8); push(&head, 6); push(&head, 10); int n = 2; cout << "Sum of last " << n << " nodes = " << sumOfLastN_NodesUtil(head, n); return 0; } |
JAVA
// Java implementation to find the sum of // last 'n' nodes of the Linked List import java.util.*; class GFG { /* A Linked list node */ static class Node { int data; Node next; }; static Node head; static int n, sum; // function to insert a node at the // beginning of the linked list static void 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; head = head_ref; } // function to recursively find the sum of last // 'n' nodes of the given linked list static void sumOfLastN_Nodes(Node head) { // if head = NULL if (head == null ) return ; // recursively traverse the remaining nodes sumOfLastN_Nodes(head.next); // if node count 'n' is greater than 0 if (n > 0 ) { // accumulate sum sum = sum + head.data; // reduce node count 'n' by 1 --n; } } // utility function to find the sum of last 'n' nodes static int sumOfLastN_NodesUtil(Node head, int n) { // if n == 0 if (n <= 0 ) return 0 ; sum = 0 ; // find the sum of last 'n' nodes sumOfLastN_Nodes(head); // required sum return sum; } // Driver Code public static void main(String[] args) { head = null ; // create linked list 10.6.8.4.12 push(head, 12 ); push(head, 4 ); push(head, 8 ); push(head, 6 ); push(head, 10 ); n = 2 ; System.out.print( "Sum of last " + n + " nodes = " + sumOfLastN_NodesUtil(head, n)); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 implementation to find the sum of # last 'n' nodes of the Linked List # Linked List node class Node: def __init__( self , data): self .data = data self . next = None head = None n = 0 sum = 0 # function to insert a node at the # beginning of the linked list def push(head_ref, new_data): global head # allocate node new_node = Node( 0 ) # 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 head = head_ref # function to recursively find the sum of last # 'n' nodes of the given linked list def sumOfLastN_Nodes(head): global sum global n # if head = None if (head = = None ): return # recursively traverse the remaining nodes sumOfLastN_Nodes(head. next ) # if node count 'n' is greater than 0 if (n > 0 ) : # accumulate sum sum = sum + head.data # reduce node count 'n' by 1 n = n - 1 # utility function to find the sum of last 'n' nodes def sumOfLastN_NodesUtil(head, n): global sum # if n == 0 if (n < = 0 ): return 0 sum = 0 # find the sum of last 'n' nodes sumOfLastN_Nodes(head) # required sum return sum # Driver Code head = None # create linked list 10.6.8.4.12 push(head, 12 ) push(head, 4 ) push(head, 8 ) push(head, 6 ) push(head, 10 ) n = 2 print ( "Sum of last " , n , " nodes = " , sumOfLastN_NodesUtil(head, n)) # This code is contributed by Arnab Kundu |
C#
// C# implementation to find the sum of // last 'n' nodes of the Linked List using System; class GFG { /* A Linked list node */ public class Node { public int data; public Node next; }; static Node head; static int n, sum; // function to insert a node at the // beginning of the linked list static void 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; head = head_ref; } // function to recursively find the sum of last // 'n' nodes of the given linked list static void sumOfLastN_Nodes(Node head) { // if head = NULL if (head == null ) return ; // recursively traverse the remaining nodes sumOfLastN_Nodes(head.next); // if node count 'n' is greater than 0 if (n > 0) { // accumulate sum sum = sum + head.data; // reduce node count 'n' by 1 --n; } } // utility function to find the sum of last 'n' nodes static int sumOfLastN_NodesUtil(Node head, int n) { // if n == 0 if (n <= 0) return 0; sum = 0; // find the sum of last 'n' nodes sumOfLastN_Nodes(head); // required sum return sum; } // Driver Code public static void Main(String[] args) { head = null ; // create linked list 10.6.8.4.12 push(head, 12); push(head, 4); push(head, 8); push(head, 6); push(head, 10); n = 2; Console.Write( "Sum of last " + n + " nodes = " + sumOfLastN_NodesUtil(head, n)); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // JavaScript implementation to find the sum of // last 'n' nodes of the Linked List /* A Linked list node */ class Node { constructor() { this .data; this .next; } } let head; let n, sum; // function to insert a node at the // beginning of the linked list function push(head_ref,new_data) { /* allocate node */ let 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; head = head_ref; } // function to recursively find the sum of last // 'n' nodes of the given linked list function sumOfLastN_Nodes(head) { // if head = NULL if (head == null ) return ; // recursively traverse the remaining nodes sumOfLastN_Nodes(head.next); // if node count 'n' is greater than 0 if (n > 0) { // accumulate sum sum = sum + head.data; // reduce node count 'n' by 1 --n; } } // utility function to find the sum of last 'n' nodes function sumOfLastN_NodesUtil(head,n) { // if n == 0 if (n <= 0) return 0; sum = 0; // find the sum of last 'n' nodes sumOfLastN_Nodes(head); // required sum return sum; } // Driver Code head = null ; // create linked list 10.6.8.4.12 push(head, 12); push(head, 4); push(head, 8); push(head, 6); push(head, 10); n = 2; document.write( "Sum of last " + n + " nodes = " + sumOfLastN_NodesUtil(head, n)); // This code is contributed by unknown2108 </script> |
输出：
Sum of last 2 nodes = 16
时间复杂性： O（n），其中n是链表中的节点数。 辅助空间： O（n），如果正在考虑系统调用堆栈。
方法2（使用用户定义堆栈的迭代方法） 这是一个迭代过程，与中解释的递归方法不同 方法1 属于 这 邮递从左向右遍历节点。遍历时，将节点推送到用户定义的堆栈。然后砰的一声打开顶部 N 从堆栈中提取并添加值。
C++
// C++ implementation to find the sum of last // 'n' 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; } // utility function to find the sum of last 'n' nodes int sumOfLastN_NodesUtil( struct Node* head, int n) { // if n == 0 if (n <= 0) return 0; stack< int > st; int sum = 0; // traverses the list from left to right while (head != NULL) { // push the node's data onto the stack 'st' st.push(head->data); // move to next node head = head->next; } // pop 'n' nodes from 'st' and // add them while (n--) { sum += st.top(); st.pop(); } // required sum return sum; } // Driver program to test above int main() { struct Node* head = NULL; // create linked list 10->6->8->4->12 push(&head, 12); push(&head, 4); push(&head, 8); push(&head, 6); push(&head, 10); int n = 2; cout << "Sum of last " << n << " nodes = " << sumOfLastN_NodesUtil(head, n); return 0; } |
JAVA
// Java implementation to find the sum of last // 'n' nodes of the Linked List import java.util.*; class GFG { /* 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; } // utility function to find the sum of last 'n' nodes static int sumOfLastN_NodesUtil(Node head, int n) { // if n == 0 if (n <= 0 ) return 0 ; Stack<Integer> st = new Stack<Integer>(); int sum = 0 ; // traverses the list from left to right while (head != null ) { // push the node's data onto the stack 'st' st.push(head.data); // move to next node head = head.next; } // pop 'n' nodes from 'st' and // add them while (n-- > 0 ) { sum += st.peek(); st.pop(); } // required sum return sum; } // Driver program to test above public static void main(String[] args) { Node head = null ; // create linked list 10.6.8.4.12 head = push(head, 12 ); head = push(head, 4 ); head = push(head, 8 ); head = push(head, 6 ); head = push(head, 10 ); int n = 2 ; System.out.print( "Sum of last " + n+ " nodes = " + sumOfLastN_NodesUtil(head, n)); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 implementation to find the sum of # last 'n' nodes of the Linked List # Linked List node class Node: def __init__( self , data): self .data = data self . next = None head = None n = 0 sum = 0 # function to insert a node at the # beginning of the linked list def push(head_ref, new_data): global head # allocate node new_node = Node( 0 ) # 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 head = head_ref # utility function to find the sum of last 'n' nodes def sumOfLastN_NodesUtil(head, n): global sum # if n == 0 if (n < = 0 ): return 0 st = [] sum = 0 # traverses the list from left to right while (head ! = None ): # push the node's data onto the stack 'st' st.append(head.data) # move to next node head = head. next # pop 'n' nodes from 'st' and # add them while (n): n - = 1 sum + = st[ 0 ] st.pop( 0 ) # required sum return sum # Driver Code head = None # create linked list 10.6.8.4.12 push(head, 12 ) push(head, 4 ) push(head, 8 ) push(head, 6 ) push(head, 10 ) n = 2 print ( "Sum of last" , n , "nodes =" , sumOfLastN_NodesUtil(head, n)) # This code is contributed by shubhamsingh10 |
C#
// C# implementation to find the sum of last // 'n' nodes of the Linked List using System; using System.Collections.Generic; class GFG { /* A Linked list node */ 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; } // utility function to find the sum of last 'n' nodes static int sumOfLastN_NodesUtil(Node head, int n) { // if n == 0 if (n <= 0) return 0; Stack< int > st = new Stack< int >(); int sum = 0; // traverses the list from left to right while (head != null ) { // push the node's data onto the stack 'st' st.Push(head.data); // move to next node head = head.next; } // pop 'n' nodes from 'st' and //.Add them while (n-- >0) { sum += st.Peek(); st.Pop(); } // required sum return sum; } // Driver code public static void Main(String[] args) { Node head = null ; // create linked list 10.6.8.4.12 head = push(head, 12); head = push(head, 4); head = push(head, 8); head = push(head, 6); head = push(head, 10); int n = 2; Console.Write( "Sum of last " + n+ " nodes = " + sumOfLastN_NodesUtil(head, n)); } } // This code is contributed by 29AjayKumar |
Javascript
<script> // Javascript implementation to find the sum of last // 'n' nodes of the Linked List /* A Linked list node */ class Node { constructor() { let data,next; } } // function to insert a node at the // beginning of the linked list function push(head_ref,new_data) { /* allocate node */ let 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; } // utility function to find the sum of last 'n' nodes function sumOfLastN_NodesUtil(head,n) { // if n == 0 if (n <= 0) return 0; let st = []; let sum = 0; // traverses the list from left to right while (head != null ) { // push the node's data onto the stack 'st' st.push(head.data); // move to next node head = head.next; } // pop 'n' nodes from 'st' and // add them while (n-- >0) { sum += st[st.length-1]; st.pop(); } // required sum return sum; } // Driver program to test above let head = null ; // create linked list 10.6.8.4.12 head = push(head, 12); head = push(head, 4); head = push(head, 8); head = push(head, 6); head = push(head, 10); let n = 2; document.write( "Sum of last " + n+ " nodes = " + sumOfLastN_NodesUtil(head, n)); // This code is contributed by patel2127 </script> |
输出：
Sum of last 2 nodes = 16
时间复杂性： O（n），其中n是链表中的节点数。 辅助空间： O（n），堆栈大小
方法3（反转链表） 以下是步骤：
- 反转给定的链表。
- 穿过第一个 N 反向链表的节点。
- 在遍历时添加它们。
- 将链接列表反转回其原始顺序。
- 返回加起来的总数。
C++
// C++ implementation to find the sum of last // 'n' 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; } void reverseList( struct Node** head_ref) { struct Node* current, *prev, *next; current = *head_ref; prev = NULL; while (current != NULL) { next = current->next; current->next = prev; prev = current; current = next; } *head_ref = prev; } // utility function to find the sum of last 'n' nodes int sumOfLastN_NodesUtil( struct Node* head, int n) { // if n == 0 if (n <= 0) return 0; // reverse the linked list reverseList(&head); int sum = 0; struct Node* current = head; // traverse the 1st 'n' nodes of the reversed // linked list and add them while (current != NULL && n--) { // accumulate node's data to 'sum' sum += current->data; // move to next node current = current->next; } // reverse back the linked list reverseList(&head); // required sum return sum; } // Driver program to test above int main() { struct Node* head = NULL; // create linked list 10->6->8->4->12 push(&head, 12); push(&head, 4); push(&head, 8); push(&head, 6); push(&head, 10); int n = 2; cout << "Sum of last " << n << " nodes = " << sumOfLastN_NodesUtil(head, n); return 0; } |
JAVA
// Java implementation to find the sum of last // 'n' nodes of the Linked List import java.util.*; class GFG { /* A Linked list node */ static class Node { int data; Node next; }; static Node head; // function to insert a node at the // beginning of the linked list static void 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; head=head_ref; } static void reverseList(Node head_ref) { Node current, prev, next; current = head_ref; prev = null ; while (current != null ) { next = current.next; current.next = prev; prev = current; current = next; } head_ref = prev; head = head_ref; } // utility function to find the sum of last 'n' nodes static int sumOfLastN_NodesUtil( int n) { // if n == 0 if (n <= 0 ) return 0 ; // reverse the linked list reverseList(head); int sum = 0 ; Node current = head; // traverse the 1st 'n' nodes of the reversed // linked list and add them while (current != null && n-- > 0 ) { // accumulate node's data to 'sum' sum += current.data; // move to next node current = current.next; } // reverse back the linked list reverseList(head); // required sum return sum; } // Driver code public static void main(String[] args) { // create linked list 10.6.8.4.12 push(head, 12 ); push(head, 4 ); push(head, 8 ); push(head, 6 ); push(head, 10 ); int n = 2 ; System.out.println( "Sum of last " + n + " nodes = " + sumOfLastN_NodesUtil(n)); } } /* This code is contributed by PrinciRaj1992 */ |
Python3
# Python implementation to find the sum of last # 'n' Nodes of the Linked List ''' A Linked list Node ''' # A Linked list Node class Node: def __init__( self , x): self .data = x self . next = None head = 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 point to the new Node head_ref = new_Node head = head_ref return head def reverseList(): global head; current, prev, next = None , None , None ; current = head; prev = None ; while (current ! = None ): next = current. next ; current. next = prev; prev = current; current = next ; head = prev; # utility function to find the sum of last 'n' Nodes def sumOfLastN_NodesUtil(n): # if n == 0 if (n < = 0 ): return 0 ; # reverse the linked list reverseList(); sum = 0 ; current = head; # traverse the 1st 'n' Nodes of the reversed # linked list and add them while (current ! = None and n > 0 ): # accumulate Node's data to 'sum' sum + = current.data; # move to next Node current = current. next ; n - = 1 ; # reverse back the linked list reverseList(); # required sum return sum ; # Driver code if __name__ = = '__main__' : # create linked list 10.6.8.4.12 # create linked list 10.6.8.4.12 head = push(head, 12 ) head = push(head, 4 ) head = push(head, 8 ) head = push(head, 6 ) head = push(head, 10 ) n = 2 ; print ( "Sum of last " , n , " Nodes = " , sumOfLastN_NodesUtil(n)); # This code contributed by Princi Singh |
C#
// C# implementation to find the sum of last // 'n' nodes of the Linked List using System; class GFG { /* A Linked list node */ public class Node { public int data; public Node next; }; static Node head; // function to insert a node at the // beginning of the linked list static void 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; head=head_ref; } static void reverseList(Node head_ref) { Node current, prev, next; current = head_ref; prev = null ; while (current != null ) { next = current.next; current.next = prev; prev = current; current = next; } head_ref = prev; head = head_ref; } // utility function to find the sum of last 'n' nodes static int sumOfLastN_NodesUtil( int n) { // if n == 0 if (n <= 0) return 0; // reverse the linked list reverseList(head); int sum = 0; Node current = head; // traverse the 1st 'n' nodes of the reversed // linked list and add them while (current != null && n-- >0) { // accumulate node's data to 'sum' sum += current.data; // move to next node current = current.next; } // reverse back the linked list reverseList(head); // required sum return sum; } // Driver code public static void Main(String[] args) { // create linked list 10->6->8->4->12 push(head, 12); push(head, 4); push(head, 8); push(head, 6); push(head, 10); int n = 2; Console.WriteLine( "Sum of last " + n + " nodes = " + sumOfLastN_NodesUtil(n)); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // javascript implementation to find the sum of last // 'n' nodes of the Linked List /* A Linked list node */ class Node { constructor() { this .data = 0; this .next = null ; } } var head; // 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; head=head_ref; } function reverseList(head_ref) { var current, prev, next; current = head_ref; prev = null ; while (current != null ) { next = current.next; current.next = prev; prev = current; current = next; } head_ref = prev; head = head_ref; } // utility function to find the sum of last 'n' nodes function sumOfLastN_NodesUtil(n) { // if n == 0 if (n <= 0) return 0; // reverse the linked list reverseList(head); var sum = 0; var current = head; // traverse the 1st 'n' nodes of the reversed // linked list and add them while (current != null && n-- >0) { // accumulate node's data to 'sum' sum += current.data; // move to next node current = current.next; } // reverse back the linked list reverseList(head); // required sum return sum; } // Driver code // create linked list 10.6.8.4.12 push(head, 12); push(head, 4); push(head, 8); push(head, 6); push(head, 10); var n = 2; document.write( "Sum of last " + n + " nodes = " + sumOfLastN_NodesUtil(n)); // This code contributed by umadevi9616 </script> |
输出：
Sum of last 2 nodes = 16
时间复杂性： O（n），其中n是链表中的节点数。 辅助空间： O（1）
方法4（使用 链接列表的长度） 以下是步骤：
- 计算给定链表的长度。顺其自然 伦恩 .
- 首先，遍历 （len-n） 从头开始。
- 然后穿过剩下的 N 节点，并在遍历时添加它们。
- 返回加起来的总数。
C++
// C++ implementation to find the sum of last // 'n' 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; } // utility function to find the sum of last 'n' nodes int sumOfLastN_NodesUtil( struct Node* head, int n) { // if n == 0 if (n <= 0) return 0; int sum = 0, len = 0; struct Node* temp = head; // calculate the length of the linked list while (temp != NULL) { len++; temp = temp->next; } // count of first (len - n) nodes int c = len - n; temp = head; // just traverse the 1st 'c' nodes while (temp != NULL && c--) // move to next node temp = temp->next; // now traverse the last 'n' nodes and add them while (temp != NULL) { // accumulate node's data to sum sum += temp->data; // move to next node temp = temp->next; } // required sum return sum; } // Driver program to test above int main() { struct Node* head = NULL; // create linked list 10->6->8->4->12 push(&head, 12); push(&head, 4); push(&head, 8); push(&head, 6); push(&head, 10); int n = 2; cout << "Sum of last " << n << " nodes = " << sumOfLastN_NodesUtil(head, n); return 0; } |
JAVA
// Java implementation to find the sum of last // 'n' nodes of the Linked List class GFG { /* A Linked list node */ static class Node { int data; Node next; }; static Node head; // function to insert a node at the // beginning of the linked list static void 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; head = head_ref; } // utility function to find the sum of last 'n' nodes static int sumOfLastN_NodesUtil(Node head, int n) { // if n == 0 if (n <= 0 ) return 0 ; int sum = 0 , len = 0 ; Node temp = head; // calculate the length of the linked list while (temp != null ) { len++; temp = temp.next; } // count of first (len - n) nodes int c = len - n; temp = head; // just traverse the 1st 'c' nodes while (temp != null &&c-- > 0 ) { // move to next node temp = temp.next; } // now traverse the last 'n' nodes and add them while (temp != null ) { // accumulate node's data to sum sum += temp.data; // move to next node temp = temp.next; } // required sum return sum; } // Driver code public static void main(String[] args) { // create linked list 10.6.8.4.12 push(head, 12 ); push(head, 4 ); push(head, 8 ); push(head, 6 ); push(head, 10 ); int n = 2 ; System.out.println( "Sum of last " + n + " nodes = " + sumOfLastN_NodesUtil(head, n)); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 implementation to find the sum # of last 'n' Nodes of the Linked List # A Linked list Node class Node: def __init__( self , x): self .data = x self . next = None head = 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 poto the new Node head_ref = new_Node head = head_ref return head # Utility function to find the sum of # last 'n' Nodes def sumOfLastN_NodesUtil(head, n): # If n == 0 if (n < = 0 ): return 0 sum = 0 len = 0 temp = head # Calculate the length of the linked list while (temp ! = None ): len + = 1 temp = temp. next # Count of first (len - n) Nodes c = len - n temp = head # Just traverse the 1st 'c' Nodes while (temp ! = None and c > 0 ): # Move to next Node temp = temp. next c - = 1 # Now traverse the last 'n' Nodes # and add them while (temp ! = None ): # Accumulate Node's data to sum sum + = temp.data # Move to next Node temp = temp. next # Required sum return sum # Driver code if __name__ = = '__main__' : # Create linked list 10->6->8->4->12 head = push(head, 12 ) head = push(head, 4 ) head = push(head, 8 ) head = push(head, 6 ) head = push(head, 10 ) n = 2 print ( "Sum of last " , n, " Nodes = " , sumOfLastN_NodesUtil(head, n)) # This code is contributed by Princi Singh |
C#
// C# implementation to find the sum of last // 'n' nodes of the Linked List using System; class GFG { /* A Linked list node */ public class Node { public int data; public Node next; }; static Node head; // function to insert a node at the // beginning of the linked list static void 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; head = head_ref; } // utility function to find the sum of last 'n' nodes static int sumOfLastN_NodesUtil(Node head, int n) { // if n == 0 if (n <= 0) return 0; int sum = 0, len = 0; Node temp = head; // calculate the length of the linked list while (temp != null ) { len++; temp = temp.next; } // count of first (len - n) nodes int c = len - n; temp = head; // just traverse the 1st 'c' nodes while (temp != null &&c-- >0) { // move to next node temp = temp.next; } // now traverse the last 'n' nodes and add them while (temp != null ) { // accumulate node's data to sum sum += temp.data; // move to next node temp = temp.next; } // required sum return sum; } // Driver code public static void Main(String[] args) { // create linked list 10.6.8.4.12 push(head, 12); push(head, 4); push(head, 8); push(head, 6); push(head, 10); int n = 2; Console.WriteLine( "Sum of last " + n + " nodes = " + sumOfLastN_NodesUtil(head, n)); } } // This code is contributed by Princi Singh |
Javascript
<script> // Javascript implementation to // find the sum of last // 'n' nodes of the Linked List /* A Linked list node */ class Node { constructor() { this .data = 0; this .next = null ; } } var head; // function to insert a node at the // beginning of the linked list function push( head_ref , new_data) { /* allocate 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; head = head_ref; } // utility function to find // the sum of last 'n' nodes function sumOfLastN_NodesUtil( head , n) { // if n == 0 if (n <= 0) return 0; var sum = 0, len = 0; temp = head; // calculate the length of the linked list while (temp != null ) { len++; temp = temp.next; } // count of first (len - n) nodes var c = len - n; temp = head; // just traverse the 1st 'c' nodes while (temp != null && c-- > 0) { // move to next node temp = temp.next; } // now traverse the last 'n' // nodes and add them while (temp != null ) { // accumulate node's data to sum sum += temp.data; // move to next node temp = temp.next; } // required sum return sum; } // Driver code // create linked list 10.6.8.4.12 push(head, 12); push(head, 4); push(head, 8); push(head, 6); push(head, 10); var n = 2; document.write( "Sum of last " + n + " nodes = " + sumOfLastN_NodesUtil(head, n)); // This code contributed by umadevi9616 </script> |
输出：
Sum of last 2 nodes = 16
时间复杂性： O（n），其中n是链表中的节点数。 辅助空间： O（1）
方法5（使用两个指针需要一次遍历） 维护两个指针——参考指针和主指针。初始化指向head的引用和主指针。首先，将引用指针移动到 N 头节点和遍历节点时，会将节点的数据累积到某个变量，例如 总和 .现在同时移动两个指针，直到引用指针到达列表的末尾，并在遍历时将所有节点的数据累积到 总和 由引用指针指向，并将所有节点的数据累积到某个变量， 临时雇员 ，由主指针指向。现在 （总和——临时） 是最后一个的所需总和 N 节点。
C++
// C++ implementation to find the sum of last // 'n' 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; } // utility function to find the sum of last 'n' nodes int sumOfLastN_NodesUtil( struct Node* head, int n) { // if n == 0 if (n <= 0) return 0; int sum = 0, temp = 0; struct Node* ref_ptr, *main_ptr; ref_ptr = main_ptr = head; // traverse 1st 'n' nodes through 'ref_ptr' and // accumulate all node's data to 'sum' while (ref_ptr != NULL && n--) { sum += ref_ptr->data; // move to next node ref_ptr = ref_ptr->next; } // traverse to the end of the linked list while (ref_ptr != NULL) { // accumulate all node's data to 'temp' pointed // by the 'main_ptr' temp += main_ptr->data; // accumulate all node's data to 'sum' pointed by // the 'ref_ptr' sum += ref_ptr->data; // move both the pointers to their respective // next nodes main_ptr = main_ptr->next; ref_ptr = ref_ptr->next; } // required sum return (sum - temp); } // Driver program to test above int main() { struct Node* head = NULL; // create linked list 10->6->8->4->12 push(&head, 12); push(&head, 4); push(&head, 8); push(&head, 6); push(&head, 10); int n = 2; cout << "Sum of last " << n << " nodes = " << sumOfLastN_NodesUtil(head, n); return 0; } |
JAVA
// Java implementation to find the sum of last // 'n' nodes of the Linked List class GfG { // Defining structure static class Node { int data; Node next; } static Node head; static void printList(Node start) { Node temp = start; while (temp != null ) { System.out.print(temp.data + " " ); temp = temp.next; } System.out.println(); } // Push function static void push(Node start, int info) { // Allocating node Node node = new Node(); // Info into node node.data = info; // Next of new node to head node.next = start; // head points to new node head = node; } private static int sumOfLastN_NodesUtil(Node head, int n) { // if n == 0 if (n <= 0 ) return 0 ; int sum = 0 , temp = 0 ; Node ref_ptr, main_ptr; ref_ptr = main_ptr = head; // traverse 1st 'n' nodes through 'ref_ptr' and // accumulate all node's data to 'sum' while (ref_ptr != null && (n--) > 0 ) { sum += ref_ptr.data; // move to next node ref_ptr = ref_ptr.next; } // traverse to the end of the linked list while (ref_ptr != null ) { // accumulate all node's data to 'temp' pointed // by the 'main_ptr' temp += main_ptr.data; // accumulate all node's data to 'sum' pointed by // the 'ref_ptr' sum += ref_ptr.data; // move both the pointers to their respective // next nodes main_ptr = main_ptr.next; ref_ptr = ref_ptr.next; } // required sum return (sum - temp); } // Driver code public static void main(String[] args) { head = null ; // Adding elements to Linked List push(head, 12 ); push(head, 4 ); push(head, 8 ); push(head, 6 ); push(head, 10 ); printList(head); int n = 2 ; System.out.println( "Sum of last " + n + " nodes = " + sumOfLastN_NodesUtil(head, n)); } } // This code is contributed by shubham96301 |
Python3
# Python3 implementation to find the sum of last # 'n' nodes of the Linked List # include class Node: def __init__( self , x): self .data = x 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) #/* link the old list to the new node */ new_node. next = head_ref #/* move the head to poto the new node */ head_ref = new_node return head_ref # utility function to find the sum of last 'n' nodes def sumOfLastN_NodesUtil(head, n): # if n == 0 if (n < = 0 ): return 0 sum = 0 temp = 0 ref_ptr = None main_ptr = None ref_ptr = main_ptr = head # traverse 1st 'n' nodes through 'ref_ptr' and # accumulate all node's data to 'sum' while (ref_ptr ! = None and n): sum + = ref_ptr.data # move to next node ref_ptr = ref_ptr. next n - = 1 # traverse to the end of the linked list while (ref_ptr ! = None ): # accumulate all node's data to 'temp' pointed # by the 'main_ptr' temp + = main_ptr.data # accumulate all node's data to 'sum' pointed by # the 'ref_ptr' sum + = ref_ptr.data # move both the pointers to their respective # next nodes main_ptr = main_ptr. next ref_ptr = ref_ptr. next # required sum return ( sum - temp) # Driver program to test above if __name__ = = '__main__' : head = None # create linked list 10.6.8.4.12 head = push(head, 12 ) head = push(head, 4 ) head = push(head, 8 ) head = push(head, 6 ) head = push(head, 10 ) n = 2 print ( "Sum of last " ,n, " nodes = " ,sumOfLastN_NodesUtil(head, n)) # This code is contributed by mohit kumar 29 |
C#
// C# implementation to find the sum of last // 'n' nodes of the Linked List using System; class GfG { // Defining structure public class Node { public int data; public Node next; } static Node head; static void printList(Node start) { Node temp = start; while (temp != null ) { Console.Write(temp.data + " " ); temp = temp.next; } Console.WriteLine(); } // Push function static void push(Node start, int info) { // Allocating node Node node = new Node(); // Info into node node.data = info; // Next of new node to head node.next = start; // head points to new node head = node; } private static int sumOfLastN_NodesUtil(Node head, int n) { // if n == 0 if (n <= 0) return 0; int sum = 0, temp = 0; Node ref_ptr, main_ptr; ref_ptr = main_ptr = head; // traverse 1st 'n' nodes through 'ref_ptr' and // accumulate all node's data to 'sum' while (ref_ptr != null && (n--) > 0) { sum += ref_ptr.data; // move to next node ref_ptr = ref_ptr.next; } // traverse to the end of the linked list while (ref_ptr != null ) { // accumulate all node's data to 'temp' pointed // by the 'main_ptr' temp += main_ptr.data; // accumulate all node's data to 'sum' pointed by // the 'ref_ptr' sum += ref_ptr.data; // move both the pointers to their respective // next nodes main_ptr = main_ptr.next; ref_ptr = ref_ptr.next; } // required sum return (sum - temp); } // Driver code public static void Main(String[] args) { head = null ; // Adding elements to Linked List push(head, 12); push(head, 4); push(head, 8); push(head, 6); push(head, 10); printList(head); int n = 2; Console.WriteLine( "Sum of last " + n + " nodes = " + sumOfLastN_NodesUtil(head, n)); } } // This code contributed by Rajput-Ji |
Javascript
<script> // Javascript implementation to find the sum of last // 'n' nodes of the Linked List // Defining structure class Node { constructor() { let node,next; } } let head; function printList(start) { let temp = start; while (temp != null ) { document.write(temp.data + " " ); temp = temp.next; } document.write( "<br>" ); } // Push function function push(start,info) { // Allocating node let node = new Node(); // Info into node node.data = info; // Next of new node to head node.next = start; // head points to new node head = node; } function sumOfLastN_NodesUtil(head,n) { // if n == 0 if (n <= 0) return 0; let sum = 0, temp = 0; let ref_ptr, main_ptr; ref_ptr = main_ptr = head; // traverse 1st 'n' nodes through 'ref_ptr' and // accumulate all node's data to 'sum' while (ref_ptr != null && (n--) > 0) { sum += ref_ptr.data; // move to next node ref_ptr = ref_ptr.next; } // traverse to the end of the linked list while (ref_ptr != null ) { // accumulate all node's data to 'temp' pointed // by the 'main_ptr' temp += main_ptr.data; // accumulate all node's data to 'sum' pointed by // the 'ref_ptr' sum += ref_ptr.data; // move both the pointers to their respective // next nodes main_ptr = main_ptr.next; ref_ptr = ref_ptr.next; } // required sum return (sum - temp); } // Driver code head = null ; // Adding elements to Linked List push(head, 12); push(head, 4); push(head, 8); push(head, 6); push(head, 10); let n = 2; document.write( "Sum of last " + n + " nodes = " + sumOfLastN_NodesUtil(head, n)); // This code is contributed by avanitrachhadiya2155 </script> |
输出：
Sum of last 2 nodes = 16
时间复杂性： O（n），其中n是链表中的节点数。 辅助空间： O（1）
本文由 阿尤什·焦哈里 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
