Construct a Maximum Sum Linked List out of two Sorted Linked Lists having some common nodes

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


#include
using 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.

Previous post Check If A Linked List Is Circular Linked List
Next post Circular Linked List Traversal

Leave a Reply

Your email address will not be published. Required fields are marked *