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

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;
}

 

 

Translate ยป