{"id":4096,"date":"2021-08-20T08:19:16","date_gmt":"2021-08-20T08:19:16","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=4096"},"modified":"2022-06-16T10:03:03","modified_gmt":"2022-06-16T10:03:03","slug":"construct-a-maximum-sum-linked-list-out-of-two-sorted-linked-lists-having-some-common-nodes","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/construct-a-maximum-sum-linked-list-out-of-two-sorted-linked-lists-having-some-common-nodes\/","title":{"rendered":"Construct a Maximum Sum Linked List out of two Sorted Linked Lists having some common nodes"},"content":{"rendered":"<p><img decoding=\"async\" src=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645528645568-maximum%20sum%20linked%20list.png\" alt=\"\" \/><\/p>\n<h3>Problem statement<\/h3>\n<p>Given two sorted linked lists, derive a linked list that contains the maximum sum path using both the linked lists. The resultant list can contain nodes from both input lists.<\/p>\n<\/p>\n<p>When constructing the result list, we may switch to the other input list only at the point of intersection (which means the two nodes with the same value in the two lists).<\/p>\n<p>Try avoiding the use of extra space.<\/p>\n<h3>Problem Statement Understanding<\/h3>\n<p>To understand the given problem, let&#8217;s take an example:<br \/>\nLet us consider 2 sorted linked lists a and b as:<br \/>\n<strong>List a<\/strong>  = <\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/08\/list-A.png\" alt=\"\" \/><\/p>\n<p><strong>List b<\/strong>  =  <\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/08\/list-b.png\" alt=\"\" \/><\/p>\n<p>We need to construct a maximum sum linked list out of them, and we are allowed to jump between the lists at their points of intersection. At each point of intersection, we have two choices: <\/p>\n<ul>\n<li>Either we can continue in the same linked list, <\/li>\n<li>Or we may switch to the other linked list. <\/li>\n<\/ul>\n<p>We have to make these choices such as to form the linked list with maximum sum.<\/p>\n<p>So for the given linked lists, our maximum sum linked list will be:<br \/>\n<strong>resultant maximum sum linked list<\/strong>:<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/08\/output-3.png\" alt=\"\" \/><\/p>\n<p>In the resultant maximum sum linked list.<\/p>\n<ul>\n<li>1\u21923 is from list a.<\/li>\n<li>Switching occurs at 3 to list b.<\/li>\n<li>12\u219242\u219290  are from list b.<\/li>\n<li>No switching occurred at point of intersection 90.<\/li>\n<li>125\u2192240 is from list b.<\/li>\n<li>Switching occurs at 240 to list a.<\/li>\n<li>517 is from list a.<\/li>\n<\/ul>\n<p>We switch from a list y to list x only when the sum of consecutive nodes in list x between a pair of nodes in greater than the sum of consecutive nodes in list y between the same pair of nodes.<\/p>\n<p><strong>Explanation<\/strong><br \/>\nFrom the above linked list a and b, we can see that:<\/p>\n<ul>\n<li>Between the common pair (3,90), the sum of nodes in list a = (31) while the sum of nodes in list b = (12+42) = 54. So as we can see that the sum of consecutive nodes in b is greater than that in a, that\u2019s why while forming the maximum sum linked list we switched from list a to list b at point of intersection 3.<\/li>\n<\/ul>\n<p>I hope from the above example it is clear what we have to do in the problem. So now, before jumping to the approach, try to think how will you approach this problem?<\/p>\n<p>It\u2019s okay if your approach is brute force, we will try to optimize it together.<\/p>\n<p>Let\u2019s have a glance at the approach.<\/p>\n<h3>Approach<\/h3>\n<p>Now, how do we approach such a problem? <\/p>\n<ul>\n<li>The idea here is to keep track of the sum between two common nodes, along with pointers to the start and end of the region. <\/li>\n<li>Compare the sums and select the larger sum region among the two. <\/li>\n<li>And then make the pointer at the end of our answer region point to the max sum region. Update the answer region.<\/li>\n<\/ul>\n<p>Now let\u2019s look at a step-by-step algorithm for the above approach.<\/p>\n<h3>Algorithm<\/h3>\n<ul>\n<li>Initialize pointers to keep track of the current region under consideration in both the linked lists, and also to maintain the start and end of our answer.<br \/>\n<strong>pa=ca=NULL<\/strong> (for current region in linked list a)<br \/>\n<strong>pb=cb=NULL<\/strong> (for current region in linked list b)<br \/>\n<strong>ans=ans_end=NULL<\/strong><\/li>\n<li>Now iterate in both the linked list, using <strong>ca<\/strong> and <strong>cb<\/strong>, till the nodes become equal and store the sum of nodes in <strong>suma<\/strong>, and <strong>sumb<\/strong>.<\/li>\n<li>Since the linked lists are sorted, we will move forward in the linked list whose current node has a smaller value.<\/li>\n<li>At the end of each region, compare the two sums.<\/li>\n<li>For the first iteration, set <strong>ans<\/strong> to the larger sum linked list in that iteration and <strong>ans_end<\/strong> to the end pointer of that region (either <strong>ca<\/strong> or <strong>cb<\/strong> depending on the sum).<\/li>\n<li>For the rest of the iterations, set next of <strong>ans_end<\/strong> to point to the larger sum region( <strong>ans_end-&gt;next = pb<\/strong> if <strong>sumb&gt;suma<\/strong> else <strong>ans_end-&gt;next = pa<\/strong>).<\/li>\n<li>Update <strong>ans_end<\/strong> as the end of the selected region (<strong>ans_end=cb<\/strong> if <strong>sumb&gt;suma<\/strong> else <strong>ans_end=ca<\/strong>) and make <strong>ca = ca-&gt;next<\/strong> and <strong>cb=cb-&gt;next<\/strong>. Finally make <strong>pa = ca<\/strong> and <strong>pb = cb<\/strong> to store the beginning of the next region in a and b respectively.<\/li>\n<li>Repeat steps 2 to 7 until we reach the end of both the linked lists.<\/li>\n<li>In the end, we will have our maximum sum linked list pointed by <strong>ans<\/strong>.<\/li>\n<\/ul>\n<p>This way, our algorithm will find the required maximum sum linked list in O(n+m) time and O(1) space.<\/p>\n<h3>Dry Run<\/h3>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/08\/Construct-a-Maximum-Sum-Linked-List-out-of-two-Sorted-Linked-Lists-having-some-common-nodes-1.png\" alt=\"\" \/><\/p>\n<p><img decoding=\"async\" src=\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/08\/Construct-a-Maximum-Sum-Linked-List-out-of-two-Sorted-Linked-Lists-having-some-common-nodes-2.png\" alt=\"\" \/><\/p>\n<h3>Code Implementation<\/h3>\n\t\t\t\t\t\t<style>\r\n\t\t\t\t\r\n\t\t\t\t\t#tab_container_8521 {\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_8521 .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_8521 .wpsm_nav-tabs {\r\n    border-bottom: 0px solid #ddd;\r\n}\r\n#tab_container_8521 .wpsm_nav-tabs > li.active > a, #tab_container_8521 .wpsm_nav-tabs > li.active > a:hover, #tab_container_8521 .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_8521 .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_8521 .wpsm_nav-tabs > li > a:focus {\r\noutline: 0px !important;\r\n}\r\n\r\n#tab_container_8521 .wpsm_nav-tabs > li > a:before {\r\n\tdisplay:none !important;\r\n}\r\n#tab_container_8521 .wpsm_nav-tabs > li > a:after {\r\n\tdisplay:none !important ;\r\n}\r\n#tab_container_8521 .wpsm_nav-tabs > li{\r\npadding:0px !important ;\r\nmargin:0px;\r\n}\r\n\r\n#tab_container_8521 .wpsm_nav-tabs > li > a:hover , #tab_container_8521 .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_8521 .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_8521 .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_8521 .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_8521 .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_8521 .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_8521 .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_8521 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_8521 .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_8521 .wpsm_nav-tabs > li {\r\n\t\t\t\t\r\n\t}\r\n\t#tab_container_8521 .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_8521 .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_8521\" >\r\n\t \r\n\t\t\t\t\t<ul class=\"wpsm_nav wpsm_nav-tabs\" role=\"tablist\" id=\"myTab_8521\">\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_8521_1\" aria-controls=\"tabs_desc_8521_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_8521_2\" aria-controls=\"tabs_desc_8521_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_8521_3\" aria-controls=\"tabs_desc_8521_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_8521_4\" aria-controls=\"tabs_desc_8521_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_8521\">\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_8521_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<stdio.h>\r\n#include<stdlib.h>\r\n\r\nstruct Node\r\n{\r\n    int data; \/\/data belong to that node\r\n    struct Node *next; \/\/next pointer\r\n};\r\n \r\n\/\/ Push the data to the head of the linked list\r\nvoid push(struct Node **head, int data)\r\n{\r\n    \/\/Allocation memory to the new node\r\n    struct Node* newnode = (struct Node*)malloc(sizeof(struct Node));\r\n \r\n    \/\/Assigning data to the new node\r\n    newnode->data = data;\r\n \r\n    \/\/Adjusting next pointer of the new node\r\n    newnode->next = *head;\r\n \r\n    \/\/New node becomes the head of the list\r\n    *head = newnode;\r\n}\r\n \r\n\/\/ Method that adjusts the pointers and prints the final list\r\nvoid finalMaxSumList(struct Node *a,struct  Node *b)\r\n{\r\n    struct Node *result = NULL;\r\n \r\n    \/\/ Assigning pre and cur to the head of the\r\n    \/\/ linked list.\r\n    struct Node *pre1 = a;\r\n    struct Node *curr1 = a;\r\n    struct Node *pre2 = b;\r\n    struct Node *curr2 = b;\r\n \r\n    \/\/ Till either of the current pointers is not\r\n    \/\/ NULL execute the loop\r\n    while (curr1 != NULL || curr2 != NULL)\r\n    {\r\n        \/\/ Keeping 2 local variables at the start of every\r\n        \/\/ loop run to keep track of the sum between pre\r\n        \/\/ and cur pointer elements.\r\n        int sum1 = 0, sum2 = 0;\r\n \r\n        \/\/ Calculating sum by traversing the nodes of linked\r\n        \/\/ list as the merging of two linked list.  The loop\r\n        \/\/ stops at a common node\r\n        while (curr1!=NULL && curr2!=NULL && curr1->data!=curr2->data)\r\n        {\r\n            if (curr1->data < curr2->data)\r\n            {\r\n                sum1 += curr1->data;\r\n                curr1 = curr1->next;\r\n            }\r\n            else \/\/ (curr2->data < curr1->data)\r\n            {\r\n                sum2 += curr2->data;\r\n                curr2 = curr2->next;\r\n            }\r\n        }\r\n \r\n        \/\/ If either of current pointers becomes NULL\r\n        \/\/ carry on the sum calculation for other one.\r\n        if (curr1 == NULL)\r\n        {\r\n            while (curr2 != NULL)\r\n            {\r\n                sum2 += curr2->data;\r\n                curr2 = curr2->next;\r\n            }\r\n        }\r\n        if (curr2 == NULL)\r\n        {\r\n            while (curr1 != NULL)\r\n            {\r\n                sum1 += curr1->data;\r\n                curr1 = curr1->next;\r\n            }\r\n        }\r\n \r\n        \/\/ First time adjustment of resultant head based on\r\n        \/\/ the maximum sum.\r\n        if (pre1 == a && pre2 == b)\r\n            result = (sum1 > sum2)? pre1 : pre2;\r\n \r\n        \/\/ If pre1 and pre2 don't contain the head pointers of\r\n        \/\/ lists adjust the next pointers of previous pointers.\r\n        else\r\n        {\r\n            if (sum1 > sum2)\r\n                pre2->next = pre1->next;\r\n            else\r\n                pre1->next = pre2->next;\r\n        }\r\n \r\n        \/\/ Adjusting previous pointers\r\n        pre1 = curr1, pre2 = curr2;\r\n \r\n        \/\/ If curr1 is not NULL move to the next.\r\n        if (curr1)\r\n            curr1 = curr1->next;\r\n        \/\/ If curr2 is not NULL move to the next.\r\n        if (curr2)\r\n            curr2 = curr2->next;\r\n    }\r\n \r\n    \/\/ Print the resultant list.\r\n    while (result != NULL)\r\n    {\r\n        printf(\"%d \", result->data);\r\n        result = result->next;\r\n    }\r\n}\r\n \r\n\/\/Main driver program\r\nint main()\r\n{\r\n    \/\/Linked List 1 : 1->3->30->90->110->120->NULL\r\n    \/\/Linked List 2 : 0->3->12->32->90->100->120->130->NULL\r\n    struct Node *head1 = NULL, *head2 = NULL;\r\n    push(&head1, 120);\r\n    push(&head1, 110);\r\n    push(&head1, 90);\r\n    push(&head1, 30);\r\n    push(&head1, 3);\r\n    push(&head1, 1);\r\n \r\n    push(&head2, 130);\r\n    push(&head2, 120);\r\n    push(&head2, 100);\r\n    push(&head2, 90);\r\n    push(&head2, 32);\r\n    push(&head2, 12);\r\n    push(&head2, 3);\r\n    push(&head2, 0);\r\n \r\n    finalMaxSumList(head1, head2);\r\n    return 0;\r\n}\r\n<\/pre>\r\n<!-- \/wp:enlighter\/codeblock -->\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_8521_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<iostream>\r\nusing namespace std;\r\n\r\nstruct Node{\r\n    int val;\r\n    Node *next;\r\n\r\n    Node(int x){ val = x; next = NULL;}\r\n};\r\n\r\nvoid push_front(Node **head, int x){\r\n    Node* temp = new Node(x);\r\n    temp->next = *head;\r\n    *head = temp;\r\n}\r\n\r\nvoid printit(Node *head){\r\n    cout<<\"head -> \";\r\n    while(head){\r\n        cout<<head->val<<\" -> \";\r\n        head = head->next;\r\n    }\r\n    cout<<\"NULL &#92;n\";\r\n}\r\n\r\n\r\nNode* maxsumlist(Node* a, Node* b){\r\n    Node *ca, *cb;\r\n    Node *pa, *pb;\r\n    ca = pa = a;\r\n    cb = pb = b;\r\n\r\n    Node *ans = NULL, *ans_end = NULL;\r\n    while(ca!=NULL || cb!=NULL){\r\n        int suma = 0, sumb = 0;\r\n    \r\n    \/\/ to calculate sums between two common nodes in\r\n    \/\/ the two linked lists\r\n        while(ca!=NULL && cb!=NULL && ca->val!=cb->val){\r\n            if(ca->val < cb->val){\r\n                suma += ca->val;\r\n                ca = ca->next;\r\n            } else {\r\n                sumb += cb->val;\r\n                cb = cb->next;\r\n            }\r\n        }\r\n\r\n        if(ca==NULL || cb==NULL){\r\n            while(ca){\r\n                suma += ca->val;\r\n                ca = ca->next;\r\n            }\r\n            while(cb){\r\n                sumb += cb->val;\r\n                cb = cb->next;\r\n            }\r\n        }\r\n\r\n        \/\/ if it is our first traversal\r\n        if( pa == a || pb == b){\r\n            if(suma > sumb){\r\n                ans = pa;\r\n                ans_end = ca;\r\n            } else {\r\n                ans = pb;\r\n                ans_end = cb;\r\n            }\r\n        }\r\n        else {\r\n            if(suma > sumb){\r\n                ans_end->next = pa;\r\n                ans_end = ca;\r\n            } else {\r\n                ans_end->next = pb;\r\n                ans_end = cb;\r\n            }\r\n        }\r\n\r\n        if(ca) ca = ca->next;\r\n        if(cb) cb = cb->next;\r\n        \r\n        pa = ca;\r\n        pb = cb;\r\n    }\r\n    \r\n    return ans;\r\n}\r\n\r\nint main()\r\n{\r\n    Node *a, *b;\r\n    a = b = NULL;\r\n    push_front(&a,517);\r\n    push_front(&a,240);\r\n    push_front(&a,121);\r\n    push_front(&a,90);\r\n    push_front(&a,31);\r\n    push_front(&a,3);\r\n    push_front(&a,1);\r\n\r\n    push_front(&b,249);\r\n    push_front(&b,240);\r\n    push_front(&b,125);\r\n    push_front(&b,90);\r\n    push_front(&b,42);\r\n    push_front(&b,12);\r\n    push_front(&b,3);\r\n    push_front(&b,-1);\r\n\r\n    Node* ans = maxsumlist(a,b);\r\n    printit(ans);\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_8521_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 MaxSum\r\n{\r\n    Node head;\r\n    class Node\r\n    {\r\n        int data;\r\n        Node next;\r\n        Node(int d)\r\n        {\r\n            data = d;\r\n            next = null;\r\n        }\r\n    }\r\n \r\n    \/\/ Method to adjust pointers and print final list\r\n    void MaxSumList(Node a, Node b)\r\n    {\r\n        Node result = null;\r\n \r\n        \r\n        Node pre1 = a, curr1 = a;\r\n        Node pre2 = b, curr2 = b;\r\n \r\n        while (curr1 != null || curr2 != null)\r\n        {\r\n            int sum1 = 0, sum2 = 0;\r\n \r\n            \/\/ to calculate sums between two common nodes in\r\n            \/\/ the two linked lists\r\n            while (curr1 != null && curr2 != null &&\r\n                   curr1.data != curr2.data)\r\n            {\r\n \r\n                if (curr1.data<curr2.data) {=\"\" sum1=\"\" +=\"curr1.data;\" curr1=\"curr1.next;\" }=\"\" else=\"\" sum2=\"\" curr2=\"curr2.next;\" if=\"\" either=\"\" of=\"\" current=\"\" pointers=\"\" becomes=\"\" null=\"\" carry=\"\" on=\"\" the=\"\" sum=\"\" calculation=\"\" for=\"\" other=\"\" one.=\"\" (curr1=\"=\" null)=\"\" while=\"\" (curr2=\"\" !=\"null)\" while(curr1=\"\" it=\"\" is=\"\" our=\"\" first=\"\" traversal=\"\" (pre1=\"=\" a=\"\" &&=\"\" pre2=\"=\" b)=\"\" result=\"(sum1\"> sum2) ? pre1 : pre2;\r\n\r\n            else\r\n            {\r\n                if (sum1 > sum2)\r\n                    pre2.next = pre1.next;\r\n                else\r\n                    pre1.next = pre2.next;\r\n            }\r\n            pre1 = curr1;\r\n            pre2 = curr2;\r\n \r\n            if (curr1 != null)\r\n                curr1 = curr1.next;\r\n \r\n            if (curr2 != null)\r\n                curr2 = curr2.next;\r\n        }\r\n \r\n        while (result != null)\r\n        {\r\n            System.out.print(result.data + \" \");\r\n            result = result.next;\r\n        }\r\n        System.out.println();\r\n    }\r\n    void push(int new_data)\r\n    {\r\n        Node new_node = new Node(new_data);\r\n        new_node.next = head;\r\n        head = new_node;\r\n    }\r\n \r\n \r\n    \/* Driver code *\/\r\n    public static void main(String args[])\r\n    {\r\n        MaxSum llist1 = new MaxSum();\r\n        MaxSum llist2 = new MaxSum();\r\n \r\n        llist1.push(517);\r\n        llist1.push(240);\r\n        llist1.push(121);\r\n        llist1.push(90);\r\n        llist1.push(31);\r\n        llist1.push(3);\r\n        llist1.push(1);\r\n        llist2.push(249);\r\n        llist2.push(240);\r\n        llist2.push(125);\r\n        llist2.push(90);\r\n        llist2.push(42);\r\n        llist2.push(12);\r\n        llist2.push(3);\r\n        llist2.push(-1);\r\n \r\n        llist1.MaxSumList(llist1.head, llist2.head);\r\n    }\r\n}\r\n<\/pre>\r\n<!-- \/wp:enlighter\/codeblock -->\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_8521_4\">\r\n\t\t\t\t\t\t\t\t\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_8521 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_8521 a\"),jQuery(\"#tab-content_8521\"));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<h3>Output<\/h3>\n<p>1 3 12 42 90 125 240 517<\/p>\n<p><strong>Time Complexity:<\/strong> O(n+m), since we are traversing both the linked lists once.<br \/>\n[forminator_quiz id=&#8221;4098&#8243;]<br \/>\nHere n and m are the total numbers of nodes in the given linked lists.<\/p>\n<p>So, in this article, we have understood how to construct a Maximum Sum Linked List out of two Sorted Linked Lists. This is an important question when it comes to coding interviews. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link <a href=\"https:\/\/mycode.prepbytes.com\/interview-coding\/practice\/linked-list\">Linked List<\/a>.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem statement Given two sorted linked lists, derive a linked list that contains the maximum sum path using both the linked lists. The resultant list can contain nodes from both input lists. When constructing the result list, we may switch to the other input list only at the point of intersection (which means the two [&hellip;]<\/p>\n","protected":false},"author":52,"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-4096","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>Construct a Maximum Sum Linked List out of two Sorted Linked Lists with common nodes | Linked List | Prepbytes<\/title>\n<meta name=\"description\" content=\"Learn how to construct a Maximum Sum Linked List out of two Sorted Linked Lists. So, in this article, we have understood how to construct a Maximum Sum Linked List out of two Sorted Linked Lists.\" \/>\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\/construct-a-maximum-sum-linked-list-out-of-two-sorted-linked-lists-having-some-common-nodes\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Construct a Maximum Sum Linked List out of two Sorted Linked Lists with common nodes | Linked List | Prepbytes\" \/>\n<meta property=\"og:description\" content=\"Learn how to construct a Maximum Sum Linked List out of two Sorted Linked Lists. So, in this article, we have understood how to construct a Maximum Sum Linked List out of two Sorted Linked Lists.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/prepbytes.com\/blog\/construct-a-maximum-sum-linked-list-out-of-two-sorted-linked-lists-having-some-common-nodes\/\" \/>\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-08-20T08:19:16+00:00\" \/>\n<meta property=\"article:modified_time\" content=\"2022-06-16T10:03:03+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645528645568-maximum%20sum%20linked%20list.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=\"4 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/prepbytes.com\/blog\/construct-a-maximum-sum-linked-list-out-of-two-sorted-linked-lists-having-some-common-nodes\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/construct-a-maximum-sum-linked-list-out-of-two-sorted-linked-lists-having-some-common-nodes\/\"},\"author\":{\"name\":\"Prepbytes\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e\"},\"headline\":\"Construct a Maximum Sum Linked List out of two Sorted Linked Lists having some common nodes\",\"datePublished\":\"2021-08-20T08:19:16+00:00\",\"dateModified\":\"2022-06-16T10:03:03+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/construct-a-maximum-sum-linked-list-out-of-two-sorted-linked-lists-having-some-common-nodes\/\"},\"wordCount\":866,\"commentCount\":0,\"publisher\":{\"@id\":\"http:\/\/43.205.93.38\/#organization\"},\"image\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/construct-a-maximum-sum-linked-list-out-of-two-sorted-linked-lists-having-some-common-nodes\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645528645568-maximum%20sum%20linked%20list.png\",\"articleSection\":[\"Linked list articles\"],\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"CommentAction\",\"name\":\"Comment\",\"target\":[\"https:\/\/prepbytes.com\/blog\/construct-a-maximum-sum-linked-list-out-of-two-sorted-linked-lists-having-some-common-nodes\/#respond\"]}]},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/prepbytes.com\/blog\/construct-a-maximum-sum-linked-list-out-of-two-sorted-linked-lists-having-some-common-nodes\/\",\"url\":\"https:\/\/prepbytes.com\/blog\/construct-a-maximum-sum-linked-list-out-of-two-sorted-linked-lists-having-some-common-nodes\/\",\"name\":\"Construct a Maximum Sum Linked List out of two Sorted Linked Lists with common nodes | Linked List | Prepbytes\",\"isPartOf\":{\"@id\":\"http:\/\/43.205.93.38\/#website\"},\"primaryImageOfPage\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/construct-a-maximum-sum-linked-list-out-of-two-sorted-linked-lists-having-some-common-nodes\/#primaryimage\"},\"image\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/construct-a-maximum-sum-linked-list-out-of-two-sorted-linked-lists-having-some-common-nodes\/#primaryimage\"},\"thumbnailUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645528645568-maximum%20sum%20linked%20list.png\",\"datePublished\":\"2021-08-20T08:19:16+00:00\",\"dateModified\":\"2022-06-16T10:03:03+00:00\",\"description\":\"Learn how to construct a Maximum Sum Linked List out of two Sorted Linked Lists. So, in this article, we have understood how to construct a Maximum Sum Linked List out of two Sorted Linked Lists.\",\"breadcrumb\":{\"@id\":\"https:\/\/prepbytes.com\/blog\/construct-a-maximum-sum-linked-list-out-of-two-sorted-linked-lists-having-some-common-nodes\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/prepbytes.com\/blog\/construct-a-maximum-sum-linked-list-out-of-two-sorted-linked-lists-having-some-common-nodes\/\"]}]},{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/prepbytes.com\/blog\/construct-a-maximum-sum-linked-list-out-of-two-sorted-linked-lists-having-some-common-nodes\/#primaryimage\",\"url\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645528645568-maximum%20sum%20linked%20list.png\",\"contentUrl\":\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645528645568-maximum%20sum%20linked%20list.png\"},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/prepbytes.com\/blog\/construct-a-maximum-sum-linked-list-out-of-two-sorted-linked-lists-having-some-common-nodes\/#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\":\"Construct a Maximum Sum Linked List out of two Sorted Linked Lists having some common nodes\"}]},{\"@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\/3f7dc4ae851791d5947a7f99df363d5e\",\"name\":\"Prepbytes\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"http:\/\/43.205.93.38\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/secure.gravatar.com\/avatar\/232042cd1a1ea0e982c96d2a2ec93fb70a8e864e00784491231e7bfe5a9e06b5?s=96&d=mm&r=g\",\"contentUrl\":\"https:\/\/secure.gravatar.com\/avatar\/232042cd1a1ea0e982c96d2a2ec93fb70a8e864e00784491231e7bfe5a9e06b5?s=96&d=mm&r=g\",\"caption\":\"Prepbytes\"},\"url\":\"https:\/\/prepbytes.com\/blog\/author\/gourav-jaincollegedekho-com\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Construct a Maximum Sum Linked List out of two Sorted Linked Lists with common nodes | Linked List | Prepbytes","description":"Learn how to construct a Maximum Sum Linked List out of two Sorted Linked Lists. So, in this article, we have understood how to construct a Maximum Sum Linked List out of two Sorted Linked Lists.","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\/construct-a-maximum-sum-linked-list-out-of-two-sorted-linked-lists-having-some-common-nodes\/","og_locale":"en_US","og_type":"article","og_title":"Construct a Maximum Sum Linked List out of two Sorted Linked Lists with common nodes | Linked List | Prepbytes","og_description":"Learn how to construct a Maximum Sum Linked List out of two Sorted Linked Lists. So, in this article, we have understood how to construct a Maximum Sum Linked List out of two Sorted Linked Lists.","og_url":"https:\/\/prepbytes.com\/blog\/construct-a-maximum-sum-linked-list-out-of-two-sorted-linked-lists-having-some-common-nodes\/","og_site_name":"PrepBytes Blog","article_publisher":"https:\/\/www.facebook.com\/prepbytes0211\/","article_published_time":"2021-08-20T08:19:16+00:00","article_modified_time":"2022-06-16T10:03:03+00:00","og_image":[{"url":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645528645568-maximum%20sum%20linked%20list.png","type":"","width":"","height":""}],"author":"Prepbytes","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Prepbytes","Est. reading time":"4 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/prepbytes.com\/blog\/construct-a-maximum-sum-linked-list-out-of-two-sorted-linked-lists-having-some-common-nodes\/#article","isPartOf":{"@id":"https:\/\/prepbytes.com\/blog\/construct-a-maximum-sum-linked-list-out-of-two-sorted-linked-lists-having-some-common-nodes\/"},"author":{"name":"Prepbytes","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/3f7dc4ae851791d5947a7f99df363d5e"},"headline":"Construct a Maximum Sum Linked List out of two Sorted Linked Lists having some common nodes","datePublished":"2021-08-20T08:19:16+00:00","dateModified":"2022-06-16T10:03:03+00:00","mainEntityOfPage":{"@id":"https:\/\/prepbytes.com\/blog\/construct-a-maximum-sum-linked-list-out-of-two-sorted-linked-lists-having-some-common-nodes\/"},"wordCount":866,"commentCount":0,"publisher":{"@id":"http:\/\/43.205.93.38\/#organization"},"image":{"@id":"https:\/\/prepbytes.com\/blog\/construct-a-maximum-sum-linked-list-out-of-two-sorted-linked-lists-having-some-common-nodes\/#primaryimage"},"thumbnailUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645528645568-maximum%20sum%20linked%20list.png","articleSection":["Linked list articles"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/prepbytes.com\/blog\/construct-a-maximum-sum-linked-list-out-of-two-sorted-linked-lists-having-some-common-nodes\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/prepbytes.com\/blog\/construct-a-maximum-sum-linked-list-out-of-two-sorted-linked-lists-having-some-common-nodes\/","url":"https:\/\/prepbytes.com\/blog\/construct-a-maximum-sum-linked-list-out-of-two-sorted-linked-lists-having-some-common-nodes\/","name":"Construct a Maximum Sum Linked List out of two Sorted Linked Lists with common nodes | Linked List | Prepbytes","isPartOf":{"@id":"http:\/\/43.205.93.38\/#website"},"primaryImageOfPage":{"@id":"https:\/\/prepbytes.com\/blog\/construct-a-maximum-sum-linked-list-out-of-two-sorted-linked-lists-having-some-common-nodes\/#primaryimage"},"image":{"@id":"https:\/\/prepbytes.com\/blog\/construct-a-maximum-sum-linked-list-out-of-two-sorted-linked-lists-having-some-common-nodes\/#primaryimage"},"thumbnailUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645528645568-maximum%20sum%20linked%20list.png","datePublished":"2021-08-20T08:19:16+00:00","dateModified":"2022-06-16T10:03:03+00:00","description":"Learn how to construct a Maximum Sum Linked List out of two Sorted Linked Lists. So, in this article, we have understood how to construct a Maximum Sum Linked List out of two Sorted Linked Lists.","breadcrumb":{"@id":"https:\/\/prepbytes.com\/blog\/construct-a-maximum-sum-linked-list-out-of-two-sorted-linked-lists-having-some-common-nodes\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/prepbytes.com\/blog\/construct-a-maximum-sum-linked-list-out-of-two-sorted-linked-lists-having-some-common-nodes\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/prepbytes.com\/blog\/construct-a-maximum-sum-linked-list-out-of-two-sorted-linked-lists-having-some-common-nodes\/#primaryimage","url":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645528645568-maximum%20sum%20linked%20list.png","contentUrl":"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645528645568-maximum%20sum%20linked%20list.png"},{"@type":"BreadcrumbList","@id":"https:\/\/prepbytes.com\/blog\/construct-a-maximum-sum-linked-list-out-of-two-sorted-linked-lists-having-some-common-nodes\/#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":"Construct a Maximum Sum Linked List out of two Sorted Linked Lists having some common nodes"}]},{"@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\/3f7dc4ae851791d5947a7f99df363d5e","name":"Prepbytes","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"http:\/\/43.205.93.38\/#\/schema\/person\/image\/","url":"https:\/\/secure.gravatar.com\/avatar\/232042cd1a1ea0e982c96d2a2ec93fb70a8e864e00784491231e7bfe5a9e06b5?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/232042cd1a1ea0e982c96d2a2ec93fb70a8e864e00784491231e7bfe5a9e06b5?s=96&d=mm&r=g","caption":"Prepbytes"},"url":"https:\/\/prepbytes.com\/blog\/author\/gourav-jaincollegedekho-com\/"}]}},"_links":{"self":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/4096","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\/52"}],"replies":[{"embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/comments?post=4096"}],"version-history":[{"count":7,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/4096\/revisions"}],"predecessor-version":[{"id":8522,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/posts\/4096\/revisions\/8522"}],"wp:attachment":[{"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/media?parent=4096"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/categories?post=4096"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prepbytes.com\/blog\/wp-json\/wp\/v2\/tags?post=4096"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}