Рубрики

Объединить два отсортированных связанных списка так, чтобы объединенный список был в обратном порядке

Даны два связанных списка, отсортированных в порядке возрастания. Объедините их так, чтобы список результатов находился в порядке убывания (в обратном порядке).

Примеры:

Input:  a: 5->10->15->40
        b: 2->3->20 
Output: res: 40->20->15->10->5->3->2

Input:  a: NULL
        b: 2->3->20 
Output: res: 20->3->2

Простое решение заключается в следующем.
1) Обратный первый список «а» .
2) Обратный второй список «б» .
3) Объединить два перевернутых списка .

Еще одно простое решение — сначала объединить оба списка, а затем отменить объединенный список.

Оба вышеуказанных решения требуют двух обходов связанного списка.

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

1) Initialize result list as empty: res = NULL.
2) Let 'a' and 'b' be heads first and second lists respectively.
3) While (a != NULL and b != NULL)
    a) Find the smaller of two (Current 'a' and 'b')
    b) Insert the smaller value node at the front of result.
    c) Move ahead in the list of smaller node. 
4) If 'b' becomes NULL before 'a', insert all nodes of 'a' 
   into result list at the beginning.
5) If 'a' becomes NULL before 'b', insert all nodes of 'a' 
   into result list at the beginning. 

Ниже приведена реализация вышеуказанного решения.

C / C ++

/ * Учитывая два отсортированных непустых связанных списка. Слить их в

   таким образом, что список результатов будет в обратном порядке

   заказ. Реверсирование связанного списка не допускается. Также,

   дополнительное место должно быть O (1) * /

#include<iostream>

using namespace std;

  
/ * Узел списка ссылок * /

struct Node

{

    int key;

    struct Node* next;

};

  
// даны два непустых связанных списка 'a' и 'b'
Node* SortedMerge(Node *a, Node *b)
{

    // Если оба списка пусты

    if (a==NULL && b==NULL) return NULL;

  

    // Инициализируем заголовок списка результатов

    Node *res = NULL;

  

    // Обходим оба списка, в то время как оба

    // есть узлы.

    while (a != NULL && b != NULL)

    {

        // Если текущее значение а меньше или равно

        // текущее значение b.

        if (a->key <= b->key)

        {

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

            Node *temp = a->next;

  

            // Добавить 'a' в начало списка результатов

            a->next = res;

            res = a;

  

            // двигаться вперед в первом списке

            a = temp;

        }

  

        // Если значение a больше. Ниже шаги похожи

        // выше (только «a» заменяется на «b»)

        else

        {

            Node *temp = b->next;

            b->next = res;

            res = b;

            b = temp;

        }

    }

  

    // Если второй список достиг конца, но первый список имеет

    // узлы. Добавить оставшиеся узлы первого списка в

    // перед списком результатов

    while (a != NULL)

    {

        Node *temp = a->next;

        a->next = res;

        res = a;

        a = temp;

    }

  

    // Если первый список достиг конца, но второй список имеет

    // узел. Добавить оставшиеся узлы первого списка в

    // перед списком результатов

    while (b != NULL)

    {

        Node *temp = b->next;

        b->next = res;

        res = b;

        b = temp;

    }

  

    return res;

}

  
/ * Функция для печати узлов в заданном связанном списке * /

void printList(struct Node *Node)

{

    while (Node!=NULL)

    {

        cout << Node->key << " ";

        Node = Node->next;

    }

}

  
/ * Утилита для создания нового узла с

   данный ключ * /

Node *newNode(int key)

{

    Node *temp = new Node;

    temp->key = key;

    temp->next = NULL;

    return temp;

}

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

int main()

{

    / * Начнем с пустого списка * /

    struct Node* res = NULL;

  

    / * Давайте создадим два отсортированных связанных списка для тестирования

       вышеуказанные функции. Созданные списки должны быть

         а: 5-> 10-> 15

         б: 2-> 3-> 20 * /

    Node *a = newNode(5);

    a->next = newNode(10);

    a->next->next = newNode(15);

  

    Node *b = newNode(2);

    b->next = newNode(3);

    b->next->next = newNode(20);

  

    cout << "List A before merge: \n";

    printList(a);

  

    cout << "\nList B before merge: \n";

    printList(b);

  

    / * объединить 2 LL в возрастающем порядке в порядке убывания * /

    res = SortedMerge(a, b);

  

    cout << "\nMerged Linked List is: \n";

    printList(res);

  

    return 0;

}

Джава

// Java-программа для объединения двух отсортированных связанных списков так, чтобы объединить
// список в обратном порядке

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

class LinkedList {

  

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

    static Node a, b;

  

    / * Класс узла * /

    static class Node {

  

        int data;

        Node next;

  

        // Конструктор для создания нового узла

        Node(int d) {

            data = d;

            next = null;

        }

    }

  

    void printlist(Node node) {

        while (node != null) {

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

            node = node.next;

        }

    }

  

    Node sortedmerge(Node node1, Node node2) {

          

        // если оба узла нулевые

        if (node1 == null && node2 == null) {

            return null;

        }

  

        // результирующий узел

        Node res = null;

  

        // если у них обоих есть узлы, пересекающие их

        while (node1 != null && node2 != null) {

  

            // Теперь сравниваем текущие данные обоих узлов

            if (node1.data <= node2.data) {

                Node temp = node1.next;

                node1.next = res;

                res = node1;

                node1 = temp;

            } else {

                Node temp = node2.next;

                node2.next = res;

                res = node2;

                node2 = temp;

            }

        }

  

        // Если второй список достиг конца, но первый список имеет

        // узлы. Добавить оставшиеся узлы первого списка в

        // перед списком результатов

        while (node1 != null) {

            Node temp = node1.next;

            node1.next = res;

            res = node1;

            node1 = temp;

        }

  

        // Если первый список достиг конца, но второй список имеет

        // узел. Добавить оставшиеся узлы первого списка в

        // перед списком результатов

        while (node2 != null) {

            Node temp = node2.next;

            node2.next = res;

            res = node2;

            node2 = temp;

        }

  

        return res;

  

    }

  

    public static void main(String[] args) {

  

        LinkedList list = new LinkedList();

        Node result = null;

  

        / * Давайте создадим два отсортированных связанных списка для тестирования

         вышеуказанные функции. Созданные списки должны быть

         а: 5-> 10-> 15

         б: 2-> 3-> 20 * /

        list.a = new Node(5);

        list.a.next = new Node(10);

        list.a.next.next = new Node(15);

  

        list.b = new Node(2);

        list.b.next = new Node(3);

        list.b.next.next = new Node(20);

  

        System.out.println("List a before merge :");

        list.printlist(a);

        System.out.println("");

        System.out.println("List b before merge :");

        list.printlist(b);

  

        // объединяем два отсортированных списка ссылок в порядке убывания

        result = list.sortedmerge(a, b);

        System.out.println("");

        System.out.println("Merged linked list : ");

        list.printlist(result);

  

    }

}

  
// Этот код предоставлен Mayank Jaiswal

C #

// C # программа для объединения двух отсортированных
// связанный список такой, что слился
// список в обратном порядке

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

using System;

  

class LinkedList

{

  

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

    static Node a, b;

  

    / * Класс узла * /

    public class Node

    {

        public int data;

        public Node next;

  

        // Конструктор для создания нового узла

        public Node(int d)

        {

            data = d;

            next = null;

        }

    }

  

    void printlist(Node node) 

    {

        while (node != null)

        {

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

            node = node.next;

        }

    }

  

    Node sortedmerge(Node node1, Node node2)

    {

          

        // если оба узла нулевые

        if (node1 == null && node2 == null)

        {

            return null;

        }

  

        // результирующий узел

        Node res = null;

  

        // если у них обоих есть узлы

        // представить их

        while (node1 != null && node2 != null)

        {

  

            // Теперь сравниваем текущие данные обоих узлов

            if (node1.data <= node2.data)

            {

                Node temp = node1.next;

                node1.next = res;

                res = node1;

                node1 = temp;

            

            else 

            {

                Node temp = node2.next;

                node2.next = res;

                res = node2;

                node2 = temp;

            }

        }

  

        // Если второй список достиг конца, но первый

        // список имеет узлы. Добавить оставшиеся узлы

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

        while (node1 != null

        {

            Node temp = node1.next;

            node1.next = res;

            res = node1;

            node1 = temp;

        }

  

        // Если первый список достиг конца, но второй

        // список имеет узел. Добавить оставшиеся узлы

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

        while (node2 != null)

        {

            Node temp = node2.next;

            node2.next = res;

            res = node2;

            node2 = temp;

        }

  

        return res;

  

    }

  

    // Код драйвера

    public static void Main(String[] args) 

    {

  

        LinkedList list = new LinkedList();

        Node result = null;

  

        / * Давайте создадим два отсортированных связанных списка для тестирования

        вышеуказанные функции. Созданные списки должны быть

        а: 5-> 10-> 15

        б: 2-> 3-> 20 * /

        LinkedList.a = new Node(5);

        LinkedList.a.next = new Node(10);

        LinkedList.a.next.next = new Node(15);

  

        LinkedList.b = new Node(2);

        LinkedList.b.next = new Node(3);

        LinkedList.b.next.next = new Node(20);

  

        Console.WriteLine("List a before merge :");

        list.printlist(a);

        Console.WriteLine("");

        Console.WriteLine("List b before merge :");

        list.printlist(b);

  

        // объединяем два отсортированных списка ссылок в порядке убывания

        result = list.sortedmerge(a, b);

        Console.WriteLine("");

        Console.WriteLine("Merged linked list : ");

        list.printlist(result);

  

    }

}

  
// Этот код предоставлен 29AjayKumar


Выход:

List A before merge: 
5 10 15 
List B before merge: 
2 3 20 
Merged Linked List is: 
20 15 10 5 3 2 

Это решение пересекает оба списка только один раз, не требует реверса и работает на месте.

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

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

Объединить два отсортированных связанных списка так, чтобы объединенный список был в обратном порядке

0.00 (0%) 0 votes