Dadas dos listas vinculadas ordenadas, construya una lista vinculada que contenga la ruta de suma máxima de principio a fin. La lista de resultados puede contener Nodes de ambas listas de entrada. Al construir la lista de resultados, podemos cambiar a la otra lista de entrada solo en el punto de intersección (lo que significa los dos Nodes con el mismo valor en las listas). Se le permite usar O(1) espacio extra.
Input: List1 = 1->3->30->90->120->240->511 List2 = 0->3->12->32->90->125->240->249 Output: Following is maximum sum linked list out of two input lists list = 1->3->12->32->90->125->240->511 we switch at 3 and 240 to get above maximum sum linked list
Recomendamos encarecidamente minimizar el navegador y probarlo usted mismo primero.
La idea aquí en la siguiente solución es ajustar los siguientes punteros después de los Nodes comunes.
- Comience con el encabezado de ambas listas vinculadas y encuentre el primer Node común. Use la técnica de fusión de la lista enlazada ordenada para eso.
- Mantenga un registro de la suma de los elementos también mientras hace esto y establezca el encabezado de la lista de resultados en función de la suma mayor hasta el primer Node común.
- Después de esto, hasta que los punteros actuales de ambas listas no se conviertan en NULL, debemos ajustar el siguiente de los punteros anteriores en función de una suma mayor.
De esta manera, se puede hacer en el lugar con espacio adicional constante.
La complejidad temporal de la siguiente solución es O(n).
Implementación:
C++
// C++ program to construct the maximum sum linked
// list out of two given sorted lists
#include<bits/stdc++.h>
using namespace std;
//A linked list node
struct Node
{
int data; //data belong to that node
Node *next; //next pointer
};
// Push the data to the head of the linked list
void push(Node **head, int data)
{
//Allocation memory to the new node
Node *newnode = new Node;
//Assigning data to the new node
newnode->data = data;
//Adjusting next pointer of the new node
newnode->next = *head;
//New node becomes the head of the list
*head = newnode;
}
// Method that adjusts the pointers and prints the final list
void finalMaxSumList(Node *a, Node *b)
{
Node *result = NULL;
// Assigning pre and cur to the head of the
// linked list.
Node *pre1 = a, *curr1 = a;
Node *pre2 = b, *curr2 = b;
// Till either of the current pointers is not
// NULL execute the loop
while (curr1 != NULL || curr2 != NULL)
{
// Keeping 2 local variables at the start of every
// loop run to keep track of the sum between pre
// and cur pointer elements.
int sum1 = 0, sum2 = 0;
// Calculating sum by traversing the nodes of linked
// list as the merging of two linked list. The loop
// stops at a 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;
}
}
// First time adjustment of resultant head based on
// the maximum sum.
if (pre1 == a && pre2 == b)
result = (sum1 > sum2)? pre1 : pre2;
// If pre1 and pre2 don't contain the head pointers of
// lists adjust the next pointers of previous pointers.
else
{
if (sum1 > sum2)
pre2->next = pre1->next;
else
pre1->next = pre2->next;
}
// Adjusting previous pointers
pre1 = curr1, pre2 = 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;
}
// Print the resultant list.
while (result != NULL)
{
cout << result->data << " ";
result = result->next;
}
}
//Main driver program
int main()
{
//Linked List 1 : 1->3->30->90->110->120->NULL
//Linked List 2 : 0->3->12->32->90->100->120->130->NULL
Node *head1 = NULL, *head2 = NULL;
push(&head1, 120);
push(&head1, 110);
push(&head1, 90);
push(&head1, 30);
push(&head1, 3);
push(&head1, 1);
push(&head2, 130);
push(&head2, 120);
push(&head2, 100);
push(&head2, 90);
push(&head2, 32);
push(&head2, 12);
push(&head2, 3);
push(&head2, 0);
finalMaxSumList(head1, head2);
return 0;
}
Java
// Java program to construct a Maximum Sum Linked List out of
// two Sorted Linked Lists having some Common nodes
class LinkedList
{
Node head; // head of list
/* Linked list Node*/
class Node
{
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
// Method to adjust pointers and print final list
void finalMaxSumList(Node a, Node b)
{
Node result = null;
/* assigning pre and cur to head
of the linked list */
Node pre1 = a, curr1 = a;
Node pre2 = b, curr2 = b;
/* Till either of current pointers is not null
execute the loop */
while (curr1 != null || curr2 != null)
{
// Keeping 2 local variables at the start of every
// loop run to keep track of the sum between pre
// and cur reference elements.
int sum1 = 0, sum2 = 0;
// Calculating sum by traversing the nodes of linked
// list as the merging of two linked list. The loop
// stops at a common node
while (curr1 != null && curr2 != null &&
curr1.data != curr2.data)
{
if (curr1.data<curr2.data)
{
sum1 += curr1.data;
curr1 = curr1.next;
}
else
{
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;
}
}
// First time adjustment of resultant head based on
// the maximum sum.
if (pre1 == a && pre2 == b)
result = (sum1 > sum2) ? pre1 : pre2;
// If pre1 and pre2 don't contain the head references of
// lists adjust the next pointers of previous pointers.
else
{
if (sum1 > sum2)
pre2.next = pre1.next;
else
pre1.next = pre2.next;
}
// Adjusting previous pointers
pre1 = curr1;
pre2 = curr2;
// If curr1 is not NULL move to the next.
if (curr1 != null)
curr1 = curr1.next;
// If curr2 is not NULL move to the next.
if (curr2 != null)
curr2 = curr2.next;
}
while (result != null)
{
System.out.print(result.data + " ");
result = result.next;
}
System.out.println();
}
/* Inserts a node at start of linked list */
void push(int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
/* Driver program to test above functions */
public static void main(String args[])
{
LinkedList llist1 = new LinkedList();
LinkedList llist2 = new LinkedList();
//Linked List 1 : 1->3->30->90->110->120->NULL
//Linked List 2 : 0->3->12->32->90->100->120->130->NULL
llist1.push(120);
llist1.push(110);
llist1.push(90);
llist1.push(30);
llist1.push(3);
llist1.push(1);
llist2.push(130);
llist2.push(120);
llist2.push(100);
llist2.push(90);
llist2.push(32);
llist2.push(12);
llist2.push(3);
llist2.push(0);
llist1.finalMaxSumList(llist1.head, llist2.head);
}
} /* This code is contributed by Rajat Mishra */
Python3
# Python program to construct a Maximum Sum Linked List out of # two Sorted Linked Lists having some Common nodes class LinkedList(object): def __init__(self): # head of list self.head = None # Linked list Node class Node(object): def __init__(self, d): self.data = d self.next = None # Method to adjust pointers and print final list def finalMaxSumList(self, a, b): result = None # assigning pre and cur to head # of the linked list pre1 = a curr1 = a pre2 = b curr2 = b # Till either of current pointers is not null # execute the loop while curr1 != None or curr2 != None: # Keeping 2 local variables at the start of every # loop run to keep track of the sum between pre # and cur reference elements. sum1 = 0 sum2 = 0 # Calculating sum by traversing the nodes of linked # list as the merging of two linked list. The loop # stops at a common node while curr1 != None and curr2 != None and curr1.data != curr2.data: if curr1.data < curr2.data: sum1 += curr1.data curr1 = curr1.next else: sum2 += curr2.data curr2 = curr2.next # If either of current pointers becomes null # carry on the sum calculation for other one. if curr1 == None: while curr2 != None: sum2 += curr2.data curr2 = curr2.next if curr2 == None: while curr1 != None: sum1 += curr1.data curr1 = curr1.next # First time adjustment of resultant head based on # the maximum sum. if pre1 == a and pre2 == b: result = pre1 if (sum1 > sum2) else pre2 else: # If pre1 and pre2 don't contain the head references of # lists adjust the next pointers of previous pointers. if sum1 > sum2: pre2.next = pre1.next else: pre1.next = pre2.next # Adjusting previous pointers pre1 = curr1 pre2 = curr2 # If curr1 is not NULL move to the next. if curr1 != None: curr1 = curr1.next # If curr2 is not NULL move to the next. if curr2 != None: curr2 = curr2.next while result != None: print (str(result.data),end=" ") result = result.next print () # Utility functions # Inserts a new Node at front of the list. def push(self, new_data): # 1 & 2: Allocate the Node & # Put in the data new_node = self.Node(new_data) # 3. Make next of new Node as head new_node.next = self.head # 4. Move the head to point to new Node self.head = new_node # Driver program llist1 = LinkedList() llist2 = LinkedList() # Linked List 1 : 1->3->30->90->110->120->NULL # Linked List 2 : 0->3->12->32->90->100->120->130->NULL llist1.push(120) llist1.push(110) llist1.push(90) llist1.push(30) llist1.push(3) llist1.push(1) llist2.push(130) llist2.push(120) llist2.push(100) llist2.push(90) llist2.push(32) llist2.push(12) llist2.push(3) llist2.push(0) llist1.finalMaxSumList(llist1.head, llist2.head) # This code is contributed by BHAVYA JAIN
C#
// C# program to construct a Maximum
// Sum Linked List out of two Sorted
// Linked Lists having some Common nodes
using System;
public class LinkedList
{
Node head; // head of list
/* Linked list Node*/
public class Node
{
public int data;
public Node next;
public Node(int d)
{
data = d;
next = null;
}
}
// Method to adjust pointers
// and print final list
void finalMaxSumList(Node a, Node b)
{
Node result = null;
/* assigning pre and cur to head
of the linked list */
Node pre1 = a, curr1 = a;
Node pre2 = b, curr2 = b;
/* Till either of current pointers
is not null execute the loop */
while (curr1 != null || curr2 != null)
{
// Keeping 2 local variables at the start
// of every loop run to keep track of the
// sum between pre and cur reference elements.
int sum1 = 0, sum2 = 0;
// Calculating sum by traversing the nodes of linked
// list as the merging of two linked list. The loop
// stops at a common node
while (curr1 != null && curr2 != null &&
curr1.data != curr2.data)
{
if (curr1.data<curr2.data)
{
sum1 += curr1.data;
curr1 = curr1.next;
}
else
{
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;
}
}
// First time adjustment of resultant
// head based on the maximum sum.
if (pre1 == a && pre2 == b)
result = (sum1 > sum2) ? pre1 : pre2;
// If pre1 and pre2 don't contain
// the head references of lists adjust
// the next pointers of previous pointers.
else
{
if (sum1 > sum2)
pre2.next = pre1.next;
else
pre1.next = pre2.next;
}
// Adjusting previous pointers
pre1 = curr1;
pre2 = curr2;
// If curr1 is not NULL move to the next.
if (curr1 != null)
curr1 = curr1.next;
// If curr2 is not NULL move to the next.
if (curr2 != null)
curr2 = curr2.next;
}
while (result != null)
{
Console.Write(result.data + " ");
result = result.next;
}
Console.WriteLine();
}
/* Inserts a node at start of linked list */
void push(int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
/* Driver code */
public static void Main()
{
LinkedList llist1 = new LinkedList();
LinkedList llist2 = new LinkedList();
//Linked List 1 : 1->3->30->90->110->120->NULL
//Linked List 2 : 0->3->12->32->90->100->120->130->NULL
llist1.push(120);
llist1.push(110);
llist1.push(90);
llist1.push(30);
llist1.push(3);
llist1.push(1);
llist2.push(130);
llist2.push(120);
llist2.push(100);
llist2.push(90);
llist2.push(32);
llist2.push(12);
llist2.push(3);
llist2.push(0);
llist1.finalMaxSumList(llist1.head, llist2.head);
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// javascript program to construct a Maximum Sum Linked List out of
// two Sorted Linked Lists having some Common nodes
var head; // head of list
/* Linked list Node */
class Node {
constructor(val) {
this.data = val;
this.next = null;
}
}
// Method to adjust pointers and print final list
function finalMaxSumList(a, b) {
var result = null;
/*
* assigning pre and cur to head of the linked list
*/
var pre1 = a, curr1 = a;
var pre2 = b, curr2 = b;
/*
* Till either of current pointers is not null execute the loop
*/
while (curr1 != null || curr2 != null)
{
// Keeping 2 local variables at the start of every
// loop run to keep track of the sum between pre
// and cur reference elements.
var sum1 = 0, sum2 = 0;
// Calculating sum by traversing the nodes of linked
// list as the merging of two linked list. The loop
// stops at a common node
while (curr1 != null && curr2 != null && curr1.data != curr2.data) {
if (curr1.data < curr2.data) {
sum1 += curr1.data;
curr1 = curr1.next;
} else {
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;
}
}
// First time adjustment of resultant head based on
// the maximum sum.
if (pre1 == a && pre2 == b)
result = (sum1 > sum2) ? pre1 : pre2;
// If pre1 and pre2 don't contain the head references of
// lists adjust the next pointers of previous pointers.
else {
if (sum1 > sum2)
pre2.next = pre1.next;
else
pre1.next = pre2.next;
}
// Adjusting previous pointers
pre1 = curr1;
pre2 = curr2;
// If curr1 is not NULL move to the next.
if (curr1 != null)
curr1 = curr1.next;
// If curr2 is not NULL move to the next.
if (curr2 != null)
curr2 = curr2.next;
}
while (result != null) {
document.write(result.data + " ");
result = result.next;
}
document.write();
}
/* Inserts a node at start of linked list */
function push(headl, new_data) {
/*
* 1 & 2: Allocate the Node & Put in the data
*/
var new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = headl;
/* 4. Move the head to point to new Node */
headl = new_node;
return headl;
}
/* Driver program to test above functions */
// Linked List 1 : 1->3->30->90->110->120->NULL
// Linked List 2 : 0->3->12->32->90->100->120->130->NULL
var llist1 = null; var llist2 = null;
llist1 = push(llist1,120);
llist1=push(llist1,110);
llist1=push(llist1,90);
llist1=push(llist1,30);
llist1=push(llist1,3);
llist1=push(llist1,1);
llist2=push(llist2,130);
llist2=push(llist2,120);
llist2=push(llist2,100);
llist2=push(llist2,90);
llist2=push(llist2,32);
llist2=push(llist2,12);
llist2=push(llist2,3);
llist2=push(llist2,0);
finalMaxSumList(llist1, llist2);
// This code is contributed by umadevi9616
</script>
Producción
1 3 12 32 90 110 120 130
Complejidad temporal: O(n) donde n es la longitud de la lista enlazada más grande
Espacio auxiliar: O(1)
Sin embargo, un problema en esta solución es que se cambian las listas originales.
Ejercicio:
1. Pruebe este problema cuando el espacio auxiliar no sea una restricción.
2. Pruebe este problema cuando no modificamos la lista real y creamos la lista resultante.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA