Рубрики

Создайте связанный список максимальной суммы из двух отсортированных связанных списков, имеющих несколько общих узлов

Учитывая два отсортированных связанных списка, создайте связанный список, который содержит путь максимальной суммы от начала до конца. Список результатов может содержать узлы из обоих входных списков. При построении списка результатов мы можем переключиться на другой входной список только в точке пересечения (что означает два узла с одинаковым значением в списках). Вам разрешено использовать O (1) дополнительное место.

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

Мы настоятельно рекомендуем свернуть браузер и попробовать это в первую очередь.

Идея здесь, в приведенном ниже решении, состоит в том, чтобы настроить следующие указатели после общих узлов.
1. Начните с заголовка обоих связанных списков и найдите первый общий узел. Для этого используйте технику слияния отсортированного связанного списка.
2. При этом следите за суммой элементов и устанавливайте заголовок списка результатов на основе большей суммы до первого общего узла.
3. После этого, пока текущие указатели обоих списков не станут NULL, нам нужно отрегулировать следующий из предыдущих указателей, основываясь на большей сумме.

Таким образом, это может быть сделано на месте с постоянным дополнительным пространством.
Временная сложность приведенного ниже решения составляет O (n).

C ++

// C ++ программа для построения максимальной суммы ссылок
// список из двух заданных отсортированных списков
#include<iostream>

using namespace std;

  
// узел связанного списка

struct Node

{

    int data; // данные принадлежат этому узлу

    Node *next; // следующий указатель

};

  
// Перетаскиваем данные в начало связанного списка

void push(Node **head, int data)

{

    // Выделение памяти новому узлу

    Node *newnode = new Node;

  

    // Назначаем данные новому узлу

    newnode->data = data;

  

    // Корректируем следующий указатель нового узла

    newnode->next = *head;

  

    // Новый узел становится главой списка

    *head = newnode;

}

  
// Метод, который корректирует указатели и печатает окончательный список

void finalMaxSumList(Node *a, Node *b)

{

    Node *result = NULL;

  

    // Присвоение pre и cur заголовку

    // связанный список.

    Node *pre1 = a, *curr1 = a;

    Node *pre2 = b, *curr2 = b;

  

    // Пока ни один из текущих указателей не

    // NULL выполнить цикл

    while (curr1 != NULL || curr2 != NULL)

    {

        // Сохранение 2 локальных переменных в начале каждого

        // цикл, чтобы отслеживать сумму между пред

        // и элементы указателя cur.

        int sum1 = 0, sum2 = 0;

  

        // Расчет суммы путём обхода узлов связанных

        // список как объединение двух связанных списков. Петля

        // останавливается на общем узле

        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;

            }

        }

  

        // Если любой из текущих указателей становится NULL

        // продолжить вычисление суммы для другого.

        if (curr1 == NULL)

        {

            while (curr2 != NULL)

            {

                sum2 += curr2->data;

                curr2 = curr2->next;

            }

        }

        if (curr2 == NULL)

        {

            while (curr1 != NULL)

            {

                sum1 += curr1->data;

                curr1 = curr1->next;

            }

        }

  

        // Первая настройка результирующей головки на основе

        // максимальная сумма.

        if (pre1 == a && pre2 == b)

            result = (sum1 > sum2)? pre1 : pre2;

  

        // Если pre1 и pre2 не содержат указателей заголовка

        // списки корректируют следующие указатели предыдущих указателей.

        else

        {

            if (sum1 > sum2)

                pre2->next = pre1->next;

            else

                pre1->next = pre2->next;

        }

  

        // Корректируем предыдущие указатели

        pre1 = curr1, pre2 = curr2;

  

        // Если curr1 не равен NULL, перейти к следующему.

        if (curr1)

            curr1 = curr1->next;

        // Если curr2 не равен NULL, перейти к следующему.

        if (curr2)

            curr2 = curr2->next;

    }

  

    // Распечатать результирующий список.

    while (result != NULL)

    {

        cout << result->data << " ";

        result = result->next;

    }

}

  
// Основная драйверная программа

int main()

{

    // Связанный список 1: 1-> 3-> 30-> 90-> 110-> 120-> NULL

    // Связанный список 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-программа для построения связанного списка с максимальной суммой из
// два отсортированных связанных списка, имеющих несколько общих узлов

class LinkedList

{

    Node head;  // заголовок списка

  

    / * Узел связанного списка * /

    class Node

    {

        int data;

        Node next;

        Node(int d)

        {

            data = d;

            next = null;

        }

    }

  

    // Способ настройки указателей и печати окончательного списка

    void finalMaxSumList(Node a, Node b)

    {

        Node result = null;

  

        / * назначение pre и cur для head

           связанного списка * /

        Node pre1 = a, curr1 = a;

        Node pre2 = b, curr2 = b;

  

        / * Пока ни один из текущих указателей не является нулевым

           выполнить цикл * /

        while (curr1 != null || curr2 != null)

        {

            // Сохранение 2 локальных переменных в начале каждого

            // цикл, чтобы отслеживать сумму между пред

            // и ссылочные элементы cur.

            int sum1 = 0, sum2 = 0;

  

            // Расчет суммы путём обхода узлов связанных

            // список как объединение двух связанных списков. Петля

            // останавливается на общем узле

            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 (curr1 == null)

            {

                while (curr2 != null)

                {

                    sum2 += curr2.data;

                    curr2 = curr2.next;

                }

            }

            if (curr2 == null)

            {

                while(curr1 != null)

                {

                    sum1 += curr1.data;

                    curr1 = curr1.next;

                }

            }

  

            // Первая настройка результирующей головки на основе

            // максимальная сумма.

            if (pre1 == a && pre2 == b)

                result = (sum1 > sum2) ? pre1 : pre2;

  

            // Если pre1 и pre2 не содержат ссылки на заголовки

            // списки корректируют следующие указатели предыдущих указателей.

            else

            {

                if (sum1 > sum2)

                    pre2.next = pre1.next;

                else

                    pre1.next = pre2.next;

            }

  

            // Корректируем предыдущие указатели

            pre1 = curr1;

            pre2 = curr2;

  

            // Если curr1 не равен NULL, перейти к следующему.

            if (curr1 != null)

                curr1 = curr1.next;

  

            // Если curr2 не равен NULL, перейти к следующему.

            if (curr2 != null)

                curr2 = curr2.next;

        }

  

        while (result != null)

        {

            System.out.print(result.data + " ");

            result = result.next;

        }

        System.out.println();

    }

  

    / * Вставляет узел в начале связанного списка * /

    void push(int new_data)

    {

        / * 1 & 2: выделить узел &

                  Введите данные * /

        Node new_node = new Node(new_data);

  

        / * 3. Сделать следующий новый узел в качестве головы * /

        new_node.next = head;

  

        / * 4. Переместить голову, чтобы указать на новый узел * /

        head = new_node;

    }

  

  

    / * Программа драйвера для проверки вышеуказанных функций * /

    public static void main(String args[])

    {

        LinkedList llist1 = new LinkedList();

        LinkedList llist2 = new LinkedList();

  

        // Связанный список 1: 1-> 3-> 30-> 90-> 110-> 120-> NULL

        // Связанный список 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);

    }

} / * Этот код предоставлен Раджатом Мишрой * /

питон

# Программа Python для построения связанного списка с максимальной суммой из
# два отсортированных связанных списка, имеющих несколько общих узлов

class LinkedList(object):

    def __init__(self):

     # заголовок списка

         self.head = None

  

    # Узел связанного списка

    class Node(object):

        def __init__(self, d):

            self.data = d

            self.next = None

  

    # Способ настройки указателей и печати окончательного списка

    def finalMaxSumList(self, a, b):

        result = None

        # назначение pre и cur на голову

        № связанного списка

        pre1 = a

        curr1 = a

        pre2 = b

        curr2 = b

        # Пока ни один из текущих указателей не является нулевым

        # выполнить цикл

        while curr1 != None or curr2 != None:

            # Хранение 2 локальных переменных в начале каждого

            # цикл запускается для отслеживания суммы между пред

            # и cur ссылочные элементы.

            sum1 = 0

            sum2 = 0

            # Расчет суммы путём обхода узлов связанных

            # список как объединение двух связанных списков. Петля

            # останавливается на общем узле

            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 curr1 == None:

                while curr2 != None:

                    sum2 += curr2.data

                    curr2 = curr2.next

            if curr2 == None:

                while curr1 != None:

                    sum1 += curr1.data

                    curr1 = curr1.next

            # Первая настройка результирующей головки на основе

            # максимальная сумма.

            if pre1 == a and pre2 == b:

                result = pre1 if (sum1 > sum2) else pre2

            else:

                # Если pre1 и pre2 не содержат ссылки на заголовки

                # списки корректируют следующие указатели предыдущих указателей.

                if sum1 > sum2:

                    pre2.next = pre1.next

                else:

                    pre1.next = pre2.next

            # Корректировка предыдущих указателей

            pre1 = curr1

            pre2 = curr2

            # Если curr1 не равен NULL, переходите к следующему.

            if curr1 != None:

                curr1 = curr1.next

            # Если curr2 не равен NULL, переходите к следующему.

            if curr2 != None:

                curr2 = curr2.next

  

        while result != None:

            print str(result.data),

            result = result.next

        print ''

  

    # Сервисные функции

    # Вставляет новый узел в начало списка.

    def push(self, new_data):

        # 1 & 2: выделить узел &

        # Вставьте данные

        new_node = self.Node(new_data)

        # 3. Сделать следующий из нового узла в качестве головы

        new_node.next = self.head

        # 4. Переместите голову, чтобы указать на новый узел

        self.head = new_node

  
# Драйверная программа

llist1 = LinkedList()

llist2 = LinkedList()

  
# Связанный список 1: 1-> 3-> 30-> 90-> 110-> 120-> NULL
# Связанный список 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)

  
# Этот код предоставлен BHAVYA JAIN

C #

// C # программа для построения максимума
// Сумма связанного списка из двух отсортированных
// Связанные списки, имеющие несколько общих узлов

using System;

  

public class LinkedList 

    Node head; // заголовок списка

  

    / * Узел связанного списка * /

    public class Node 

    

        public int data; 

        public Node next; 

        public Node(int d) 

        

            data = d; 

            next = null

        

    

  

    // Метод настройки указателей

    // и распечатать окончательный список

    void finalMaxSumList(Node a, Node b) 

    

        Node result = null

  

        / * назначение pre и cur для head

        связанного списка * /

        Node pre1 = a, curr1 = a; 

        Node pre2 = b, curr2 = b; 

  

        / * До одного из текущих указателей

        не равно NULL выполнить цикл * /

        while (curr1 != null || curr2 != null

        

            // Сохраняем 2 локальные переменные в начале

            // каждого цикла, чтобы отслеживать

            // сумма между ссылочными элементами pre и cur.

            int sum1 = 0, sum2 = 0; 

  

            // Расчет суммы путём обхода узлов связанных

            // список как объединение двух связанных списков. Петля

            // останавливается на общем узле

            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 (curr1 == null

            

                while (curr2 != null

                

                    sum2 += curr2.data; 

                    curr2 = curr2.next; 

                

            

            if (curr2 == null

            

                while(curr1 != null

                

                    sum1 += curr1.data; 

                    curr1 = curr1.next; 

                

            

  

            // Первая корректировка результата

            // голова на основе максимальной суммы.

            if (pre1 == a && pre2 == b) 

                result = (sum1 > sum2) ? pre1 : pre2; 

  

            // Если pre1 и pre2 не содержат

            // заголовки списков настраиваются

            // следующие указатели предыдущих указателей.

            else

            

                if (sum1 > sum2) 

                    pre2.next = pre1.next; 

                else

                    pre1.next = pre2.next; 

            

  

            // Корректируем предыдущие указатели

            pre1 = curr1; 

            pre2 = curr2; 

  

            // Если curr1 не равен NULL, перейти к следующему.

            if (curr1 != null

                curr1 = curr1.next; 

  

            // Если curr2 не равен NULL, перейти к следующему.

            if (curr2 != null

                curr2 = curr2.next; 

        

  

        while (result != null

        

            Console.Write(result.data + " "); 

            result = result.next; 

        

        Console.WriteLine(); 

    

  

    / * Вставляет узел в начале связанного списка * /

    void push(int new_data) 

    

        / * 1 & 2: выделить узел &

                Введите данные * /

        Node new_node = new Node(new_data); 

  

        / * 3. Сделать следующий новый узел в качестве головы * /

        new_node.next = head; 

  

        / * 4. Переместить голову, чтобы указать на новый узел * /

        head = new_node; 

    

  

  

    / * Код водителя * /

    public static void Main() 

    

        LinkedList llist1 = new LinkedList(); 

        LinkedList llist2 = new LinkedList(); 

  

        // Связанный список 1: 1-> 3-> 30-> 90-> 110-> 120-> NULL

        // Связанный список 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); 

    

  
/ * Этот код предоставлен PrinciRaj1992 * /


Выход:

1 3 12 32 90 110 120 130

Сложность по времени: O (n) где n — длина большего связанного списка
Вспомогательное пространство: O (1)
Однако проблема в этом решении заключается в том, что исходные списки изменены.

Упражнение
1. Попробуйте эту проблему, когда вспомогательное пространство не является ограничением.
2. Попробуйте эту проблему, когда мы не изменяем фактический список и не создаем результирующий список.

Эта статья предоставлена Кумар Гаутам . Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Создайте связанный список максимальной суммы из двух отсортированных связанных списков, имеющих несколько общих узлов

0.00 (0%) 0 votes