### 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 nodes with the same value in the two lists).

Try avoiding the use of extra space.

### Problem Statement Understanding

To understand the given problem, let's take an example:

Let us consider 2 sorted linked lists a and b as:

**List a** =

**List b** =

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:

- Either we can continue in the same linked list,
- Or we may switch to the other linked list.

We have to make these choices such as to form the linked list with maximum sum.

So for the given linked lists, our maximum sum linked list will be:

**resultant maximum sum linked list**:

In the resultant maximum sum linked list.

- 1â†’3 is from list a.
- Switching occurs at 3 to list b.
- 12â†’42â†’90 are from list b.
- No switching occurred at point of intersection 90.
- 125â†’240 is from list b.
- Switching occurs at 240 to list a.
- 517 is from list a.

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.

**Explanation**

From the above linked list a and b, we can see that:

- 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â€™s why while forming the maximum sum linked list we switched from list a to list b at point of intersection 3.

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?

Itâ€™s okay if your approach is brute force, we will try to optimize it together.

Letâ€™s have a glance at the approach.

### Approach

Now, how do we approach such a problem?

- 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.
- Compare the sums and select the larger sum region among the two.
- And then make the pointer at the end of our answer region point to the max sum region. Update the answer region.

Now letâ€™s look at a step-by-step algorithm for the above approach.

### Algorithm

- 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.

**pa=ca=NULL**(for current region in linked list a)

**pb=cb=NULL**(for current region in linked list b)

**ans=ans_end=NULL** - Now iterate in both the linked list, using
**ca**and**cb**, till the nodes become equal and store the sum of nodes in**suma**, and**sumb**. - Since the linked lists are sorted, we will move forward in the linked list whose current node has a smaller value.
- At the end of each region, compare the two sums.
- For the first iteration, set
**ans**to the larger sum linked list in that iteration and**ans_end**to the end pointer of that region (either**ca**or**cb**depending on the sum). - For the rest of the iterations, set next of
**ans_end**to point to the larger sum region(**ans_end->next = pb**if**sumb>suma**else**ans_end->next = pa**). - Update
**ans_end**as the end of the selected region (**ans_end=cb**if**sumb>suma**else**ans_end=ca**) and make**ca = ca->next**and**cb=cb->next**. Finally make**pa = ca**and**pb = cb**to store the beginning of the next region in a and b respectively. - Repeat steps 2 to 7 until we reach the end of both the linked lists.
- In the end, we will have our maximum sum linked list pointed by
**ans**.

This way, our algorithm will find the required maximum sum linked list in O(n+m) time and O(1) space.

### Dry Run

### Code Implementation

#includeusing namespace std; struct Node{ int val; Node *next; Node(int x){ val = x; next = NULL;} }; void push_front(Node **head, int x){ Node* temp = new Node(x); temp->next = *head; *head = temp; } void printit(Node *head){ cout<<"head -> "; while(head){ cout< val<<" -> "; head = head->next; } cout<<"NULL \n"; } Node* maxsumlist(Node* a, Node* b){ Node *ca, *cb; Node *pa, *pb; ca = pa = a; cb = pb = b; Node *ans = NULL, *ans_end = NULL; while(ca!=NULL || cb!=NULL){ int suma = 0, sumb = 0; // to calculate sums between two common nodes in // the two linked lists while(ca!=NULL && cb!=NULL && ca->val!=cb->val){ if(ca->val < cb->val){ suma += ca->val; ca = ca->next; } else { sumb += cb->val; cb = cb->next; } } if(ca==NULL || cb==NULL){ while(ca){ suma += ca->val; ca = ca->next; } while(cb){ sumb += cb->val; cb = cb->next; } } // if it is our first traversal if( pa == a || pb == b){ if(suma > sumb){ ans = pa; ans_end = ca; } else { ans = pb; ans_end = cb; } } else { if(suma > sumb){ ans_end->next = pa; ans_end = ca; } else { ans_end->next = pb; ans_end = cb; } } if(ca) ca = ca->next; if(cb) cb = cb->next; pa = ca; pb = cb; } return ans; } int main() { Node *a, *b; a = b = NULL; push_front(&a,517); push_front(&a,240); push_front(&a,121); push_front(&a,90); push_front(&a,31); push_front(&a,3); push_front(&a,1); push_front(&b,249); push_front(&b,240); push_front(&b,125); push_front(&b,90); push_front(&b,42); push_front(&b,12); push_front(&b,3); push_front(&b,-1); Node* ans = maxsumlist(a,b); printit(ans); }

### Output

1 3 12 42 90 125 240 517

**Time Complexity:** O(n+m), since we are traversing both the linked lists once.

Here n and m are the total numbers of nodes in the given linked lists.

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 Linked List.