{"id":3428,"date":"2021-07-26T12:49:10","date_gmt":"2021-07-26T12:49:10","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=3428"},"modified":"2022-11-22T09:17:46","modified_gmt":"2022-11-22T09:17:46","slug":"find-the-sum-of-last-n-nodes-of-the-given-linked-list","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/find-the-sum-of-last-n-nodes-of-the-given-linked-list\/","title":{"rendered":"Find the sum of last n nodes of the given Linked List"},"content":{"rendered":"<p>The Linked list is an important topic from an interview perspective. Companies like Amazon, Flipkart, Goldman Sach, Abode, Samsung, and many more asked questions over the linked lists. In this blog, we will discuss the famous problem of the linked list \u201cfind the sum of last n nodes of the linked list\u201d. Let\u2019s deep dive and solve \u201csum of nodes in linked list\u201d.<\/p>\n<p>We will be given a linked list and a number n as input and we need to find the sum of the last n nodes of the linked list.<\/p>\n<p>Let the input be the list given below and n = 3.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/07\/17_1.png\" alt=\"\" \/><\/p>\n<p>The output of the above input will be:- 58 [sum of last 3 nodes data i.e. 4,23,31]<\/p>\n<h2>Approach #1 To Find The Sum Of Last N Nodes Of The Linked List :<\/h2>\n<p>In this approach,<\/p>\n<ul>\n<li>we first calculate the length of the linked list and let it be L.<\/li>\n<li>Then, we move a pointer (initially at head )  to (L &#8211; n) nodes forward from its initial position.<\/li>\n<li>Then, traverse the remaining nodes while adding their values in a variable and return the sum variable.<\/li>\n<\/ul>\n<p><strong>Time Complexity To Find The Sum Of Last N Nodes Of The Linked List<\/strong> &#8211; O(n)<\/p>\n<p>The above approach seems good but we could do even better because we are traversing the list twice in the above approach and we could reduce it to traversing the list just once. Let\u2019s learn to do this in second approach below.<\/p>\n<h2>Approach #2 To Find The Sum Of Last N Nodes Of The Linked List:<\/h2>\n<p>In this approach,<\/p>\n<ul>\n<li>Create 2 pointers initially pointing to the head of the linked list.<\/li>\n<li>Move one pointer n nodes away from the head and accumulate sum while moving it in a variable (say sum).<\/li>\n<li>Now move both pointers by one node simultaneously till the pointer moved in step 2 becomes NULL and accumulate the sum of nodes for both the pointers in separate variables.<\/li>\n<li>Now the pointer that is ahead, has sum of all nodes of the list and the pointer that is behind, has sum of (L-n) nodes of the list (where L is the length of the linked list). So, we need to subtract both variables in order to get our result.<\/li>\n<\/ul>\n<h2>Code Implementation To Find The Sum Of Last N Nodes Of The Linked List:<\/h2>\n\t\t\t\t\t\t<style>\r\n\t\t\t\t\r\n\t\t\t\t\t#tab_container_3430 {\r\n\toverflow:hidden;\r\n\tdisplay:block;\r\n\twidth:100%;\r\n\tborder:0px solid #ddd;\r\n\tmargin-bottom:30px;\r\n\t}\r\n\r\n#tab_container_3430 .tab-content{\r\n\tpadding:20px;\r\n\tborder: 1px solid #e6e6e6 !important;\r\n\tmargin-top: 0px;\r\n\tbackground-color:#ffffff !important;\r\n\tcolor: #000000 !important;\r\n\tfont-size:16px !important;\r\n\tfont-family: Open Sans !important;\r\n\t\r\n\t\tborder: 1px solid #e6e6e6 !important;\r\n\t}\r\n#tab_container_3430 .wpsm_nav-tabs {\r\n    border-bottom: 0px solid #ddd;\r\n}\r\n#tab_container_3430 .wpsm_nav-tabs > li.active > a, #tab_container_3430 .wpsm_nav-tabs > li.active > a:hover, #tab_container_3430 .wpsm_nav-tabs > li.active > a:focus {\r\n\tcolor: #000000 !important;\r\n\tcursor: default;\r\n\tbackground-color: #ffffff !important;\r\n\tborder: 1px solid #e6e6e6 !important;\r\n}\r\n\r\n#tab_container_3430 .wpsm_nav-tabs > li > a {\r\n    margin-right: 0px !important; \r\n    line-height: 1.42857143 !important;\r\n    border: 1px solid #d5d5d5 !important;\r\n    border-radius: 0px 0px 0 0 !important; \r\n\tbackground-color: #e8e8e8 !important;\r\n\tcolor: #000000 !important;\r\n\tpadding: 15px 18px 15px 18px !important;\r\n\ttext-decoration: none !important;\r\n\tfont-size: 14px !important;\r\n\ttext-align:center !important;\r\n\tfont-family: Open Sans !important;\r\n}\r\n#tab_container_3430 .wpsm_nav-tabs > li > a:focus {\r\noutline: 0px !important;\r\n}\r\n\r\n#tab_container_3430 .wpsm_nav-tabs > li > a:before {\r\n\tdisplay:none !important;\r\n}\r\n#tab_container_3430 .wpsm_nav-tabs > li > a:after {\r\n\tdisplay:none !important ;\r\n}\r\n#tab_container_3430 .wpsm_nav-tabs > li{\r\npadding:0px !important ;\r\nmargin:0px;\r\n}\r\n\r\n#tab_container_3430 .wpsm_nav-tabs > li > a:hover , #tab_container_3430 .wpsm_nav-tabs > li > a:focus {\r\n    color: #000000 !important;\r\n    background-color: #e8e8e8 !important;\r\n\tborder: 1px solid #d5d5d5 !important;\r\n\t\r\n}\r\n#tab_container_3430 .wpsm_nav-tabs > li > a .fa{\r\n\r\nmargin-right:5px !important;\r\n\r\nmargin-left:5px !important;\r\n\r\n\r\n}\r\n\r\n\t\t#tab_container_3430 .wpsm_nav-tabs a{\r\n\t\t\tbackground-image: none;\r\n\t\t\tbackground-position: 0 0;\r\n\t\t\tbackground-repeat: repeat-x;\r\n\t\t}\r\n\t\t\t\r\n\r\n\r\n#tab_container_3430 .wpsm_nav-tabs > li {\r\n    float: left;\r\n    margin-bottom: -1px !important;\r\n\tmargin-right:0px !important; \r\n}\r\n\r\n\r\n#tab_container_3430 .tab-content{\r\noverflow:hidden !important;\r\n}\r\n\r\n\r\n@media (min-width: 769px) {\r\n\r\n\t#tab_container_3430 .wpsm_nav-tabs > li{\r\n\t\tfloat:left !important ;\r\n\t\t\t\tmargin-right:-1px !important;\r\n\t\t\t\t\t}\r\n\t#tab_container_3430 .wpsm_nav-tabs{\r\n\t\tfloat:none !important;\r\n\t\tmargin:0px !important;\r\n\t}\r\n\r\n\t#tab_container_3430 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_3430 .wpsm_nav{\r\n\t\t\t}\r\n\r\n}\r\n\r\n\r\n\r\n@media (max-width: 768px) {\r\n\t#tab_container_3430 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_3430 .wpsm_nav{\r\n\t\t\t}\r\n}\r\n\r\n\r\n\t.wpsm_nav-tabs li:before{\r\n\t\tdisplay:none !important;\r\n\t}\r\n\r\n\t@media (max-width: 768px) {\r\n\t\t\t\t\r\n\t\t\t\t.wpsm_nav-tabs{\r\n\t\t\tmargin-left:0px !important;\r\n\t\t\tmargin-right:0px !important; \r\n\t\t\t\r\n\t\t}\r\n\t\t\t\t#tab_container_3430 .wpsm_nav-tabs > li{\r\n\t\t\tfloat:none !important;\r\n\t\t}\r\n\t\t\t\r\n\t}\t\t\t\t<\/style>\r\n\t\t\t\t<div id=\"tab_container_3430\" >\r\n\t \r\n\t\t\t\t\t<ul class=\"wpsm_nav wpsm_nav-tabs\" role=\"tablist\" id=\"myTab_3430\">\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t<li role=\"presentation\"  class=\"active\"  onclick=\"do_resize()\">\r\n\t\t\t\t\t\t\t\t<a href=\"#tabs_desc_3430_1\" aria-controls=\"tabs_desc_3430_1\" role=\"tab\" data-toggle=\"tab\">\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<i class=\"fa fa-code\"><\/i> \t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t<span>C<\/span>\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t<\/a>\r\n\t\t\t\t\t\t\t<\/li>\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t<li role=\"presentation\"  onclick=\"do_resize()\">\r\n\t\t\t\t\t\t\t\t<a href=\"#tabs_desc_3430_2\" aria-controls=\"tabs_desc_3430_2\" role=\"tab\" data-toggle=\"tab\">\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<i class=\"fa fa-code\"><\/i> \t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t<span>C++<\/span>\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t<\/a>\r\n\t\t\t\t\t\t\t<\/li>\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t<li role=\"presentation\"  onclick=\"do_resize()\">\r\n\t\t\t\t\t\t\t\t<a href=\"#tabs_desc_3430_3\" aria-controls=\"tabs_desc_3430_3\" role=\"tab\" data-toggle=\"tab\">\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<i class=\"fa fa-code\"><\/i> \t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t<span>Java<\/span>\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t<\/a>\r\n\t\t\t\t\t\t\t<\/li>\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t<li role=\"presentation\"  onclick=\"do_resize()\">\r\n\t\t\t\t\t\t\t\t<a href=\"#tabs_desc_3430_4\" aria-controls=\"tabs_desc_3430_4\" role=\"tab\" data-toggle=\"tab\">\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t<i class=\"fa fa-code\"><\/i> \t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t<span>Python<\/span>\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t\t\r\n\t\t\t\t\t\t\t\t<\/a>\r\n\t\t\t\t\t\t\t<\/li>\r\n\t\t\t\t\t\t\t\t\t\t\t <\/ul>\r\n\r\n\t\t\t\t\t  <!-- Tab panes -->\r\n\t\t\t\t\t  <div class=\"tab-content\" id=\"tab-content_3430\">\r\n\t\t\t\t\t\t\t\t\t\t\t\t <div role=\"tabpanel\" class=\"tab-pane  in active \" id=\"tabs_desc_3430_1\">\r\n\t\t\t\t\t\t\t\t<!-- wp:enlighter\/codeblock {\"language\":\"c\"} -->\r\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"c\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\r\n#include&lt;stdio.h&gt;\r\n#include&lt;stdlib.h&gt;\r\n\r\nstruct Node {\r\n    int data;\r\n    struct Node* next;\r\n};\r\n \r\n\/\/ function to insert a node at the\r\n\/\/ beginning of the linked list\r\nvoid push(struct Node** head_ref, int new_data)\r\n{\r\n    \/* allocate node *\/\r\n    struct Node* new_node = malloc(sizeof(struct Node*));\r\n \r\n    \/* put in the data  *\/\r\n    new_node-&gt;data = new_data;\r\n \r\n    \/* link the old list to the new node *\/\r\n    new_node-&gt;next = (*head_ref);\r\n \r\n    \/* move the head to point to the new node *\/\r\n    (*head_ref) = new_node;\r\n}\r\n \r\n\/\/ function to recursively find the sum of last\r\n\/\/ 'n' nodes of the given linked list\r\nvoid sumOfLastN_Nodes(struct Node* head, int* n,\r\n                                      int* sum)\r\n{\r\n    \/\/ if head = NULL\r\n    if (!head)\r\n        return;\r\n \r\n    \/\/ recursively traverse the remaining nodes\r\n    sumOfLastN_Nodes(head-&gt;next, n, sum);\r\n \r\n    \/\/ if node count 'n' is greater than 0\r\n    if (*n &gt; 0) {\r\n \r\n        \/\/ accumulate sum\r\n        *sum = *sum + head-&gt;data;\r\n \r\n        \/\/ reduce node count 'n' by 1\r\n        --*n;\r\n    }\r\n}\r\n \r\n\/\/ utility function to find the sum of last 'n' nodes\r\nint sumOfLastN_NodesUtil(struct Node* head, int n)\r\n{\r\n    \/\/ if n == 0\r\n    if (n &lt;= 0)\r\n        return 0;\r\n \r\n    int sum = 0;\r\n \r\n    \/\/ find the sum of last 'n' nodes\r\n    sumOfLastN_Nodes(head, &amp;n, &amp;sum);\r\n \r\n    \/\/ required sum\r\n    return sum;\r\n}\r\n \r\n\/\/ Driver program to test above\r\nint main()\r\n{\r\n    struct Node* head = NULL;\r\n \r\n    \/\/ create linked list 10-&gt;6-&gt;8-&gt;4-&gt;12\r\n    push(&amp;head, 12);\r\n    push(&amp;head, 4);\r\n    push(&amp;head, 8);\r\n    push(&amp;head, 6);\r\n    push(&amp;head, 10);\r\n \r\n    int n = 2;\r\n    int ans = sumOfLastN_NodesUtil(head, n);\r\n\tprintf(&quot;Sum of last n Nodes %d&quot;,ans);\r\n    return 0;\r\n}\r\n\r\n<\/pre>\r\n<!-- \/wp:enlighter\/codeblock -->\r\n\t\t\t\t\t\t <\/div>\r\n\t\t\t\t\t\t\t\t\t\t\t\t <div role=\"tabpanel\" class=\"tab-pane \" id=\"tabs_desc_3430_2\">\r\n\t\t\t\t\t\t\t\t<!-- wp:enlighter\/codeblock {\"language\":\"cpp\"} -->\r\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\r\n#include&lt;bits\/stdc++.h&gt;\r\nusing namespace std;\r\n\r\nclass Node\r\n{\r\n    public:\r\n    int data;\r\n    Node* next;\r\n    Node(int x){\r\n        data = x;\r\n   next = NULL;\r\n    }\r\n};\r\n \r\nint sum_of_last_N_nodes( Node* head, int n)\r\n{\r\n    if (n &lt;= 0)\r\n        return 0;\r\n \r\n    int sum = 0, temp = 0;\r\n    Node* right_pointer, *left_pointer;\r\n    right_pointer = left_pointer = head;\r\n \r\n    \/\/ moving the right pointer n nodes to the right from head\r\n    \/\/ as discussed in step 2\r\n    while (right_pointer != NULL &amp;&amp;  n&gt;0) {                  \r\n        sum += right_pointer-&gt;data;\r\n        n--;\r\n        right_pointer = right_pointer-&gt;next;\r\n    }\r\n \r\n    \/\/ traversing the list by moving both the pointers \r\n    \/\/ simultaneously till right pointer reaches end\r\n    while (right_pointer != NULL) {\r\n \r\n        \/\/ store all node's data in 'temp' pointed\r\n        \/\/ by the 'left_pointer'\r\n        temp += left_pointer-&gt;data;\r\n \r\n        \/\/ store all node's data to 'sum' pointed by\r\n        \/\/ the 'right_pointer'\r\n        sum += right_pointer-&gt;data;\r\n \r\n        left_pointer = left_pointer-&gt;next;\r\n        right_pointer = right_pointer-&gt;next;\r\n    }\r\n \r\n    \/\/ return the difference in both variables as discussed in\r\n    \/\/ last step\r\n    return (sum - temp);\r\n}\r\n \r\nint main(void)\r\n{\r\n    Node* head = NULL;\r\n    head = new Node(7);\r\n    head-&gt;next = new Node(2);\r\n    head-&gt;next-&gt;next = new Node(4);\r\n    head-&gt;next-&gt;next-&gt;next = new Node(23);\r\n    head-&gt;-&gt;next-&gt;next-&gt;next-&gt;next = new Node(31);\r\n \r\n    cout&lt;&lt;sum_of_last_n_nodes(head,3); \r\n    return 0;\r\n}\r\n<\/pre>\r\n<!-- \/wp:enlighter\/codeblock -->\r\n\t\t\t\t\t\t <\/div>\r\n\t\t\t\t\t\t\t\t\t\t\t\t <div role=\"tabpanel\" class=\"tab-pane \" id=\"tabs_desc_3430_3\">\r\n\t\t\t\t\t\t\t\t<!-- wp:enlighter\/codeblock {\"language\":\"java\"} -->\r\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\r\nclass sum\r\n{\r\n\tstatic class Node\r\n\t{\r\n\t\tint data;\r\n\t\tNode next;\r\n\t}\r\n\r\n\tstatic Node head;\r\n\r\n\tstatic void printList(Node start)\r\n\t{\r\n\t\tNode temp = start;\r\n\t\twhile (temp != null)\r\n\t\t{\r\n\t\t\tSystem.out.print(temp.data + &quot; &quot;);\r\n\t\t\ttemp = temp.next;\r\n\t\t}\r\n\t\tSystem.out.println();\r\n\t}\r\n\tstatic void push(Node start, int info)\r\n\t{\r\n\t\tNode node = new Node();\r\n\t\tnode.data = info;\r\n\t\tnode.next = start;\r\n\t\thead = node;\r\n    }\r\n\tstatic int sumOfLastN_NodesUtil(Node head, int n)\r\n\t{\r\n\t\tif (n &lt;= 0)\r\n\t\t\treturn 0;\r\n\r\n\t\tint sum = 0, temp = 0;\r\n\t\tNode ref_ptr, main_ptr;\r\n\t\tref_ptr = main_ptr = head;\r\n\r\n\t\t\/\/ traverse 1st 'n' nodes through 'ref_ptr' and accumulate all node's data to 'sum'\r\n\t\twhile (ref_ptr != null &amp;&amp; (n--) &gt; 0)\r\n\t\t{\r\n\t\t\tsum += ref_ptr.data;\r\n\t\t\tref_ptr = ref_ptr.next;\r\n\t\t}\r\n\t\twhile (ref_ptr != null)\r\n\t\t{\r\n\t\t\ttemp += main_ptr.data;\r\n\t\t\tsum += ref_ptr.data;\r\n\t\t\tmain_ptr = main_ptr.next;\r\n\t\t\tref_ptr = ref_ptr.next;\r\n\t\t}\r\n\t\treturn (sum - temp);\r\n\t}\r\n\tpublic static void main(String[] args)\r\n\t{\r\n\t\thead = null;\r\n\r\n\t\tpush(head, 12);\r\n\t\tpush(head, 4);\r\n\t\tpush(head, 8);\r\n\t\tpush(head, 6);\r\n\t\tpush(head, 10);\r\n\r\n\t\tprintList(head);\r\n\r\n\t\tint n = 3;\r\n\r\n\t\tSystem.out.println(&quot;Sum of last &quot; + n +&quot; nodes = &quot; + sumOfLastN_NodesUtil(head, n));\r\n\t}\r\n}\r\n\r\n\r\n<\/pre>\r\n<!-- \/wp:enlighter\/codeblock -->\r\n\t\t\t\t\t\t <\/div>\r\n\t\t\t\t\t\t\t\t\t\t\t\t <div role=\"tabpanel\" class=\"tab-pane \" id=\"tabs_desc_3430_4\">\r\n\t\t\t\t\t\t\t\t<!-- wp:enlighter\/codeblock {\"language\":\"python\"} -->\r\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">\r\n\r\nclass Node:\r\n\r\n\tdef __init__(self, data):\r\n\t\tself.data = data\r\n\t\tself.next = None\r\n\r\ndef sum_of_last_n_nodes( head, n):\r\n\r\n\tif n&lt;=0:\r\n\t\treturn 0\r\n\r\n\tsum = 0\r\n\ttemp = 0\r\n\tright = left = head\r\n\twhile right and n&gt;0:\r\n\t\tsum += right.data\r\n\t\tn -= 1\r\n\t\tright = right.next\r\n\r\n\twhile right:\r\n\t\ttemp += left.data\r\n\t\tsum +=right.data\r\n\t\tleft = left.next\r\n\t\tright = right.next\r\n\treturn sum - temp\r\n\r\nhead = None\r\nhead = Node(7)\r\nhead.next = Node(2)\r\nhead.next.next = Node(4)\r\nhead.next.next.next = Node(23)\r\nhead.next.next.next.next = Node(31)\r\n\r\nprint(sum_of_last_n_nodes(head,3))\r\n<\/pre>\r\n<!-- \/wp:enlighter\/codeblock -->\r\n\t\t\t\t\t\t <\/div>\r\n\t\t\t\t\t\t\t\r\n\t\t\t\t\t <\/div>\r\n\t\t\t\t\t \r\n\t\t\t\t <\/div>\r\n <script>\r\n\t\tjQuery(function () {\r\n\t\t\tjQuery('#myTab_3430 a:first').tab('show')\r\n\t\t});\r\n\t\t\r\n\t\t\t\tjQuery(function(){\r\n\t\t\tvar b=\"fadeIn\";\r\n\t\t\tvar c;\r\n\t\t\tvar a;\r\n\t\t\td(jQuery(\"#myTab_3430 a\"),jQuery(\"#tab-content_3430\"));function d(e,f,g){\r\n\t\t\t\te.click(function(i){\r\n\t\t\t\t\ti.preventDefault();\r\n\t\t\t\t\tjQuery(this).tab(\"show\");\r\n\t\t\t\t\tvar h=jQuery(this).data(\"easein\");\r\n\t\t\t\t\tif(c){c.removeClass(a);}\r\n\t\t\t\t\tif(h){f.find(\"div.active\").addClass(\"animated \"+h);a=h;}\r\n\t\t\t\t\telse{if(g){f.find(\"div.active\").addClass(\"animated \"+g);a=g;}else{f.find(\"div.active\").addClass(\"animated \"+b);a=b;}}c=f.find(\"div.active\");\r\n\t\t\t\t});\r\n\t\t\t}\r\n\t\t});\r\n\t\t\r\n\r\n\t\tfunction do_resize(){\r\n\r\n\t\t\tvar width=jQuery( '.tab-content .tab-pane iframe' ).width();\r\n\t\t\tvar height=jQuery( '.tab-content .tab-pane iframe' ).height();\r\n\r\n\t\t\tvar toggleSize = true;\r\n\t\t\tjQuery('iframe').animate({\r\n\t\t\t    width: toggleSize ? width : 640,\r\n\t\t\t    height: toggleSize ? height : 360\r\n\t\t\t  }, 250);\r\n\r\n\t\t\t  toggleSize = !toggleSize;\r\n\t\t}\r\n\r\n\r\n\t<\/script>\r\n\t\t\t\t\r\n\t\t\t\n<pre><code>Output: 58<\/code><\/pre>\n<p><strong>Time Complexity To Find The Sum Of Last N Nodes Of The Linked List<\/strong> &#8211; O(n)<\/p>\n<p>Note that although the complexity of this approach is the same as the previous one, we are traversing the list only once in this approach rather than traversing twice.<\/p>\n<p>This blog had solved and discussed completely to find the sum of last n nodes of the linked list. This problem tests a candidate&#8217;s problem-solving skills and his or her grasp on the concepts of linked list and heap. We highly encourage you to have a good grasp of major data structures. If you want to practice more questions on linked lists, feel free to solve them at  PrepBytes <a href=\"https:\/\/mycode.prepbytes.com\/interview-coding\/practice\/linked-list\">Linked List<\/a>.<\/p>\n<h2>FAQ<\/h2>\n<p><strong>1. How do you find the last node in a linked list?<\/strong><br \/>\nThe last node of a linked list has the reference pointer as NULL. i.e. node=&gt;next = NULL. To find the last node, we have to iterate the linked till the node=&gt;next != NULL.<\/p>\n<p><strong>2. How do you sum nodes in a linked list?<\/strong><br \/>\nSo to find the sum of all elements of the singly linked list, we have to navigate to each node of the linked list and add the element&#8217;s value to a sum variable. Suppose we have a linked list: 5 -&gt; 30 -&gt; 32 -&gt; 1 -&gt; 9 sum = 5 + 30 + 32 + 1 + 9 = 77.<\/p>\n<p><strong>3. What is the last node in a linked list called?<\/strong><br \/>\nThe first node in the list is called the head, and the last node in the list is called the tail. To create a singly linked list, we first need to create a node class. Each node will have two data members: an integer value and a reference to the next node in the list.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>The Linked list is an important topic from an interview perspective. Companies like Amazon, Flipkart, Goldman Sach, Abode, Samsung, and many more asked questions over the linked lists. In this blog, we will discuss the famous problem of the linked list \u201cfind the sum of last n nodes of the linked list\u201d. Let\u2019s deep dive [&hellip;]<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[125],"tags":[],"class_list":["post-3428","post","type-post","status-publish","format-standard","hentry","category-linked-list"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v25.8 - https:\/\/yoast.com\/wordpress\/plugins\/seo\/ -->\n<title>Find the sum of last n nodes of the given Linked List | Linked list articles | PrepBytes Blog<\/title>\n<meta name=\"description\" content=\"learn the most efficient way to find sum of the last n nodes of a linked list\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/prepbytes.com\/blog\/find-the-sum-of-last-n-nodes-of-the-given-linked-list\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Find the sum of last n nodes of the given Linked List | Linked list articles | PrepBytes Blog\" \/>\n<meta property=\"og:description\" content=\"learn the most efficient way to find sum of the last n nodes of a linked list\" \/>\n<meta property=\"og:url\" content=\"https:\/\/prepbytes.com\/blog\/find-the-sum-of-last-n-nodes-of-the-given-linked-list\/\" \/>\n<meta property=\"og:site_name\" content=\"PrepBytes Blog\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/prepbytes0211\/\" \/>\n<meta property=\"article:published_time\" content=\"2021-07-26T12:49:10+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2022-11-22T09:17:46+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/07\/17_1.png\" \/>\n<meta name=\"author\" content=\"PrepBytes\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"PrepBytes\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"3 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/prepbytes.com\/blog\/find-the-sum-of-last-n-nodes-of-the-given-linked-list\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/find-the-sum-of-last-n-nodes-of-the-given-linked-list\/\"},\"author\":{\"name\":\"PrepBytes\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/39fcf072e04987f16796546f2ca83c2e\"},\"headline\":\"Find the sum of last n nodes of the given Linked List\",\"datePublished\":\"2021-07-26T12:49:10+00:00\",\"dateModified\":\"2022-11-22T09:17:46+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/find-the-sum-of-last-n-nodes-of-the-given-linked-list\/\"},\"wordCount\":688,\"commentCount\":0,\"publisher\":{\"@id\":\"http:\/\/43.205.93.38\/#organization\"},\"image\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/find-the-sum-of-last-n-nodes-of-the-given-linked-list\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/07\/17_1.png\",\"articleSection\":[\"Linked list articles\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/prepbytes.com\/blog\/find-the-sum-of-last-n-nodes-of-the-given-linked-list\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/prepbytes.com\/blog\/find-the-sum-of-last-n-nodes-of-the-given-linked-list\/\",\"url\":\"https:\/\/prepbytes.com\/blog\/find-the-sum-of-last-n-nodes-of-the-given-linked-list\/\",\"name\":\"Find the sum of last n nodes of the given Linked List | Linked list articles | PrepBytes Blog\",\"isPartOf\":{\"@id\":\"http:\/\/43.205.93.38\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/find-the-sum-of-last-n-nodes-of-the-given-linked-list\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/find-the-sum-of-last-n-nodes-of-the-given-linked-list\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/07\/17_1.png\",\"datePublished\":\"2021-07-26T12:49:10+00:00\",\"dateModified\":\"2022-11-22T09:17:46+00:00\",\"description\":\"learn the most efficient way to find sum of the last n nodes of a linked list\",\"breadcrumb\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/find-the-sum-of-last-n-nodes-of-the-given-linked-list\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/prepbytes.com\/blog\/find-the-sum-of-last-n-nodes-of-the-given-linked-list\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/prepbytes.com\/blog\/find-the-sum-of-last-n-nodes-of-the-given-linked-list\/#primaryimage\",\"url\":\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/07\/17_1.png\",\"contentUrl\":\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/07\/17_1.png\",\"width\":2619,\"height\":175},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/prepbytes.com\/blog\/find-the-sum-of-last-n-nodes-of-the-given-linked-list\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"http:\/\/43.205.93.38\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"Linked list articles\",\"item\":\"https:\/\/prepbytes.com\/blog\/category\/linked-list\/\"},{\"@type\":\"ListItem\",\"position\":3,\"name\":\"Find the sum of last n nodes of the given Linked List\"}]},{\"@type\":\"WebSite\",\"@id\":\"http:\/\/43.205.93.38\/#website\",\"url\":\"http:\/\/43.205.93.38\/\",\"name\":\"PrepBytes Blog\",\"description\":\"ONE-STOP RESOURCE FOR EVERYTHING RELATED TO CODING\",\"publisher\":{\"@id\":\"http:\/\/43.205.93.38\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"http:\/\/43.205.93.38\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Organization\",\"@id\":\"http:\/\/43.205.93.38\/#organization\",\"name\":\"Prepbytes\",\"url\":\"http:\/\/43.205.93.38\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp\",\"contentUrl\":\"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp\",\"width\":160,\"height\":160,\"caption\":\"Prepbytes\"},\"image\":{\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/\"},\"sameAs\":[\"https:\/\/www.facebook.com\/prepbytes0211\/\",\"https:\/\/www.instagram.com\/prepbytes\/\",\"https:\/\/www.linkedin.com\/company\/prepbytes\/\",\"https:\/\/www.youtube.com\/channel\/UC0xGnHDrjUM1pDEK2Ka5imA\"]},{\"@type\":\"Person\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/39fcf072e04987f16796546f2ca83c2e\",\"name\":\"PrepBytes\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/850669d326db1e1531f04db0c63145d941c2a26792aaeee226a9e6675b0ac698?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/850669d326db1e1531f04db0c63145d941c2a26792aaeee226a9e6675b0ac698?s=96&d=mm&r=g\",\"caption\":\"PrepBytes\"},\"url\":\"https:\/\/prepbytes.com\/blog\/author\/prepbytes\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Find the sum of last n nodes of the given Linked List | Linked list articles | PrepBytes Blog","description":"learn the most efficient way to find sum of the last n nodes of a linked list","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/prepbytes.com\/blog\/find-the-sum-of-last-n-nodes-of-the-given-linked-list\/","og_locale":"en_US","og_type":"article","og_title":"Find the sum of last n nodes of the given Linked List | Linked list articles | PrepBytes Blog","og_description":"learn the most efficient way to find sum of the last n nodes of a linked list","og_url":"https:\/\/prepbytes.com\/blog\/find-the-sum-of-last-n-nodes-of-the-given-linked-list\/","og_site_name":"PrepBytes Blog","article_publisher":"https:\/\/www.facebook.com\/prepbytes0211\/","article_published_time":"2021-07-26T12:49:10+00:00","article_modified_time":"2022-11-22T09:17:46+00:00","og_image":[{"url":"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/07\/17_1.png","type":"","width":"","height":""}],"author":"PrepBytes","twitter_card":"summary_large_image","twitter_misc":{"Written by":"PrepBytes","Est. reading time":"3 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/prepbytes.com\/blog\/find-the-sum-of-last-n-nodes-of-the-given-linked-list\/#article","isPartOf":{"@id":"https:\/\/prepbytes.com\/blog\/find-the-sum-of-last-n-nodes-of-the-given-linked-list\/"},"author":{"name":"PrepBytes","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/39fcf072e04987f16796546f2ca83c2e"},"headline":"Find the sum of last n nodes of the given Linked List","datePublished":"2021-07-26T12:49:10+00:00","dateModified":"2022-11-22T09:17:46+00:00","mainEntityOfPage":{"@id":"https:\/\/prepbytes.com\/blog\/find-the-sum-of-last-n-nodes-of-the-given-linked-list\/"},"wordCount":688,"commentCount":0,"publisher":{"@id":"http:\/\/43.205.93.38\/#organization"},"image":{"@id":"https:\/\/prepbytes.com\/blog\/find-the-sum-of-last-n-nodes-of-the-given-linked-list\/#primaryimage"},"thumbnailUrl":"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/07\/17_1.png","articleSection":["Linked list articles"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/prepbytes.com\/blog\/find-the-sum-of-last-n-nodes-of-the-given-linked-list\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/prepbytes.com\/blog\/find-the-sum-of-last-n-nodes-of-the-given-linked-list\/","url":"https:\/\/prepbytes.com\/blog\/find-the-sum-of-last-n-nodes-of-the-given-linked-list\/","name":"Find the sum of last n nodes of the given Linked List | Linked list articles | PrepBytes Blog","isPartOf":{"@id":"http:\/\/43.205.93.38\/#website"},"primaryImageOfPage":{"@id":"https:\/\/prepbytes.com\/blog\/find-the-sum-of-last-n-nodes-of-the-given-linked-list\/#primaryimage"},"image":{"@id":"https:\/\/prepbytes.com\/blog\/find-the-sum-of-last-n-nodes-of-the-given-linked-list\/#primaryimage"},"thumbnailUrl":"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/07\/17_1.png","datePublished":"2021-07-26T12:49:10+00:00","dateModified":"2022-11-22T09:17:46+00:00","description":"learn the most efficient way to find sum of the last n nodes of a linked list","breadcrumb":{"@id":"https:\/\/prepbytes.com\/blog\/find-the-sum-of-last-n-nodes-of-the-given-linked-list\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/prepbytes.com\/blog\/find-the-sum-of-last-n-nodes-of-the-given-linked-list\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/prepbytes.com\/blog\/find-the-sum-of-last-n-nodes-of-the-given-linked-list\/#primaryimage","url":"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/07\/17_1.png","contentUrl":"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/07\/17_1.png","width":2619,"height":175},{"@type":"BreadcrumbList","@id":"https:\/\/prepbytes.com\/blog\/find-the-sum-of-last-n-nodes-of-the-given-linked-list\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"http:\/\/43.205.93.38\/"},{"@type":"ListItem","position":2,"name":"Linked list articles","item":"https:\/\/prepbytes.com\/blog\/category\/linked-list\/"},{"@type":"ListItem","position":3,"name":"Find the sum of last n nodes of the given Linked List"}]},{"@type":"WebSite","@id":"http:\/\/43.205.93.38\/#website","url":"http:\/\/43.205.93.38\/","name":"PrepBytes Blog","description":"ONE-STOP RESOURCE FOR EVERYTHING RELATED TO CODING","publisher":{"@id":"http:\/\/43.205.93.38\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"http:\/\/43.205.93.38\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"http:\/\/43.205.93.38\/#organization","name":"Prepbytes","url":"http:\/\/43.205.93.38\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/","url":"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp","contentUrl":"https:\/\/blog.prepbytes.com\/wp-content\/uploads\/2025\/07\/uzxxllgloialmn9mhwfe.webp","width":160,"height":160,"caption":"Prepbytes"},"image":{"@id":"http:\/\/43.205.93.38\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.facebook.com\/prepbytes0211\/","https:\/\/www.instagram.com\/prepbytes\/","https:\/\/www.linkedin.com\/company\/prepbytes\/","https:\/\/www.youtube.com\/channel\/UC0xGnHDrjUM1pDEK2Ka5imA"]},{"@type":"Person","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/39fcf072e04987f16796546f2ca83c2e","name":"PrepBytes","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/850669d326db1e1531f04db0c63145d941c2a26792aaeee226a9e6675b0ac698?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/850669d326db1e1531f04db0c63145d941c2a26792aaeee226a9e6675b0ac698?s=96&d=mm&r=g","caption":"PrepBytes"},"url":"https:\/\/prepbytes.com\/blog\/author\/prepbytes\/"}]}},"_links":{"self":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/3428","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/comments?post=3428"}],"version-history":[{"count":2,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/3428\/revisions"}],"predecessor-version":[{"id":10681,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/3428\/revisions\/10681"}],"wp:attachment":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/media?parent=3428"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/categories?post=3428"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/tags?post=3428"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}