## Given two sorted linked lists, construct a list that contains maximum sum path from start to end.

The result list may 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(node with same value).

### Example

**INPUT**

list1

2->8->34->50->71->75

list2:

1->8->10->45->50->80

**OUTPUT**

2 ->8 ->10 ->45 ->50 ->71 ->75

In the above example, we can see that 8 is the first common node and 2 is the greatest sum till 8.

After 8, 50 is the next common node and 55 is the greatest sum till 50. so, 10, 45 are the elements in the result. After 50, 146 is the greatest sum so, 71, 75 are the elements in the result list

**Time Complexity : O(n)**

## Algorithm

Initialize temp1, curr1 to list1 and temp2,curr2 to list2

**1.** Traverse both lists and find the first common node(using “curr” pointer) ie, 8 in above example

**2.** Also keep track of greater sum in both lists. The head of list which has greater sum is the head of the result list(ie, using “temp” pointer). ie, 2(list1) in above example

**3.** After this, till curr pointers of both lists dont become NULL. we need to change the next of temp pointers based on greater sum

The above algorithm is clearly explained in below diagram

## C++ Proogram

```
#include <bits/stdc++.h>
using namespace std;
struct LLNode{
int data;
LLNode *next;
};
LLNode* maxSumList(LLNode* list1, LLNode* list2)
{
LLNode *result = NULL;
// Assigning temp and curr to the head of the linked list
LLNode *temp1 = list1, *curr1 = list1;
LLNode *temp2 = list2, *curr2 = list2;
// Till either of the current pointers is not
// NULL execute the loop
while (curr1 != NULL || curr2 != NULL)
{
//variables sum1, sum2 to keep track of sum between
//temp and curr in both lists
int sum1 = 0, sum2 = 0;
//calculating sum till the common node
while (curr1!=NULL && curr2!=NULL && curr1->data!=curr2->data)
{
if (curr1->data < curr2->data)
{
sum1 += curr1->data;
curr1 = curr1->next;
}
else // (curr2->data < curr1->data)
{
sum2 += curr2->data;
curr2 = curr2->next;
}
}
// If either of current pointers becomes NULL
// carry on the sum calculation for other one.
if (curr1 == NULL)
{
while (curr2 != NULL)
{
sum2 += curr2->data;
curr2 = curr2->next;
}
}
if (curr2 == NULL)
{
while (curr1 != NULL)
{
sum1 += curr1->data;
curr1 = curr1->next;
}
}
//For the first common node
//To know the head of the result list
if (temp1 == list1 && temp2 == list2)
result = (sum1 > sum2)? temp1 : temp2;
//If temp1 and temp2 are not the heads, then update next pointers
else
{
if (sum1 > sum2)
temp2->next = temp1->next;
else
temp1->next = temp2->next;
}
// updating temp pointers
temp1 = curr1, temp2 = curr2;
// If curr1 is not NULL move to the next.
if (curr1)
curr1 = curr1->next;
// If curr2 is not NULL move to the next.
if (curr2)
curr2 = curr2->next;
}
return result;
}
void insertAtBeginning(LLNode**head,int dataToBeInserted)
{
LLNode*curr=new LLNode;
//make a new LLNode with this data and next pointing to NULL
curr->data=dataToBeInserted;
curr->next=NULL;
if(*head==NULL) //if list is empty then set the current formed LLNode as head of list
*head=curr;
else //make the next of the current LLNode point to the present head and make the current LLNode as the new head
{
curr->next=*head;
*head=curr;
}
//O(1) constant time
}
void display(LLNode**head)
{
LLNode*temp=*head;
while(temp!=NULL) //till the list ends (NULL marks ending of list)
{
if(temp->next!=NULL)
cout<<temp->data<<" ->";
else
cout<<temp->data;
temp=temp->next; //move to next LLNode
}
//O(number of nodes)
cout<<endl;
}
int main()
{
LLNode *result = NULL;
LLNode *list1 = NULL; //initial list has no elements
insertAtBeginning(&list1,75);
insertAtBeginning(&list1,71);
insertAtBeginning(&list1,50);
insertAtBeginning(&list1,34);
insertAtBeginning(&list1,8);
insertAtBeginning(&list1,2);
LLNode *list2 = NULL;
insertAtBeginning(&list2,80);
insertAtBeginning(&list2,50);
insertAtBeginning(&list2,45);
insertAtBeginning(&list2,10);
insertAtBeginning(&list2,8);
insertAtBeginning(&list2,1);
cout<<"\n Two lists are :-\n";
display(&list1);
display(&list2);
result = maxSumList(list1,list2);
cout<<"Max Sum List is"<<endl;
display(&result);
return 0;
}
```