Рубрики

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

Напишите функцию SortedMerge (), которая принимает два списка, каждый из которых сортируется в порядке возрастания, и объединяет их в один список в порядке возрастания. SortedMerge () должен вернуть новый список. Новый список должен быть составлен путем сращивания
вместе узлы первых двух списков.

Например, если первый связанный список a равен 5-> 10-> 15, а другой связанный список b равен 2-> 3-> 20, то SortedMerge () должен вернуть указатель на головной узел объединенного списка 2-> 3-> 5-> 10-> 15-> 20.

Есть много случаев, с которыми приходится иметь дело: либо «a», либо «b» могут быть пустыми, во время обработки сначала могут заканчиваться «a» или «b», и, наконец, существует проблема запуска пустого списка результатов и его построения. вверх, проходя через «а» и «б».

Метод 1 (Использование фиктивных узлов)
Стратегия здесь использует временный фиктивный узел в качестве начала списка результатов. Указатель Tail всегда указывает на последний узел в списке результатов, поэтому добавление новых узлов легко.
Пустой узел дает хвосту что-то, на что он должен указывать изначально, когда список результатов пуст. Этот фиктивный узел является эффективным, поскольку он является только временным и размещается в стеке. Цикл продолжается, удаляя один узел из «a» или «b» и добавляя его в tail. когда
мы закончили, результат в dummy.next.

Ниже приведен пробный запуск вышеуказанного подхода:

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

C ++

/ * C ++ программа для объединения двух отсортированных связанных списков * /
#include <bits/stdc++.h>

using namespace std;

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

class Node 

    public:

    int data; 

    Node* next; 

}; 

  
/ * снять передний узел
источник и поместите его в dest * /

void MoveNode(Node** destRef, Node** sourceRef); 

  
/ * Принимает два списка, отсортированных по возрастанию
порядок и соединяет их узлы
сделать один большой отсортированный список, который
возвращается * /
Node* SortedMerge(Node* a, Node* b) 

    / * фиктивный первый узел для зависания результата * /

    Node dummy; 

  

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

    Node* tail = &dummy; 

  

    / * так хвост-> рядом находится место

    добавить новые узлы к результату. * /

    dummy.next = NULL; 

    while (1) 

    

        if (a == NULL) 

        

            / * если какой-либо список исчерпан, используйте

            другой список * /

            tail->next = b; 

            break

        

        else if (b == NULL) 

        

            tail->next = a; 

            break

        

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

            MoveNode(&(tail->next), &a); 

        else

            MoveNode(&(tail->next), &b); 

  

        tail = tail->next; 

    

    return(dummy.next); 

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /
/ * Функция MoveNode () принимает
узел от передней части источника,
и переместить его в переднюю часть Dest.
Ошибка вызывать это с
список источников пуст.

  
Перед вызовом MoveNode ():
источник == {1, 2, 3}
dest == {1, 2, 3}

  
Аффтер, вызывающий MoveNode ():
источник == {2, 3}
dest == {1, 1, 2, 3} * /

void MoveNode(Node** destRef, Node** sourceRef) 

    / * передний исходный узел * /

    Node* newNode = *sourceRef; 

    assert(newNode != NULL); 

  

    / * Продвигать указатель источника * /

    *sourceRef = newNode->next; 

  

    / * Свяжите старый dest с новым узлом * /

    newNode->next = *destRef; 

  

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

    *destRef = newNode; 

  

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

void push(Node** head_ref, int new_data) 

    / * выделить узел * /

    Node* new_node = new Node();

  

    / * вставить данные * /

    new_node->data = new_data; 

  

    / * связать старый список с новым узлом * /

    new_node->next = (*head_ref); 

  

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

    (*head_ref) = new_node; 

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

void printList(Node *node) 

    while (node!=NULL) 

    

        cout<<node->data<<" "

        node = node->next; 

    

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

int main() 

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

    Node* res = NULL; 

    Node* a = NULL; 

    Node* b = NULL; 

  

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

    проверить функции

    Созданные списки, a: 5-> 10-> 15, b: 2-> 3-> 20 * /

    push(&a, 15); 

    push(&a, 10); 

    push(&a, 5); 

  

    push(&b, 20); 

    push(&b, 3); 

    push(&b, 2); 

  

    / * Удалить дубликаты из связанного списка * /

    res = SortedMerge(a, b); 

  

    cout << "Merged Linked List is: \n"

    printList(res); 

  

    return 0; 

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

С

/ * C программа для объединения двух отсортированных связанных списков * /
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>

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

struct Node

{

    int data;

    struct Node* next;

};

  
/ * вытащить передний узел источника и поместить его в dest * /

void MoveNode(struct Node** destRef, struct Node** sourceRef);

  
/ * Принимает два списка, отсортированных в порядке возрастания, и сращивает

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

   возвращается * /

struct Node* SortedMerge(struct Node* a, struct Node* b)

{

    / * фиктивный первый узел для зависания результата * /

    struct Node dummy;

  

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

    struct Node* tail = &dummy;

  

    / * так что tail-> next - это место для добавления новых узлов

      к результату. * /

    dummy.next = NULL;

    while (1)

    {

        if (a == NULL)

        {

            / * если какой-либо список исчерпан, используйте

               другой список * /

            tail->next = b;

            break;

        }

        else if (b == NULL)

        {

            tail->next = a;

            break;

        }

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

            MoveNode(&(tail->next), &a);

        else

            MoveNode(&(tail->next), &b);

  

        tail = tail->next;

    }

    return(dummy.next);

}

  
/ * ПОЛЕЗНЫЕ ФУНКЦИИ * /
/ * Функция MoveNode () берет узел впереди

   источник, и переместите его в начало Dest.

   Ошибочно называть это с пустым списком источников.

  

   Перед вызовом MoveNode ():

   источник == {1, 2, 3}

   dest == {1, 2, 3}

  

   Аффтер, вызывающий MoveNode ():

   источник == {2, 3}

   dest == {1, 1, 2, 3} * /

void MoveNode(struct Node** destRef, struct Node** sourceRef)

{

    / * передний исходный узел * /

    struct Node* newNode = *sourceRef;

    assert(newNode != NULL);

  

    / * Продвигать указатель источника * /

    *sourceRef = newNode->next;

  

    / * Свяжите старый dest с новым узлом * /

    newNode->next = *destRef;

  

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

    *destRef = newNode;

}

  

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

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

void push(struct Node** head_ref, int new_data)

{

    / * выделить узел * /

    struct Node* new_node =

        (struct Node*) malloc(sizeof(struct Node));

  

    / * вставить данные * /

    new_node->data  = new_data;

  

    / * связать старый список с новым узлом * /

    new_node->next = (*head_ref);

  

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

    (*head_ref)    = new_node;

}

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

void printList(struct Node *node)

{

    while (node!=NULL)

    {

        printf("%d ", node->data);

        node = node->next;

    }

}

  
/ * Сушилка для тестирования вышеуказанных функций * /

int main()

{

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

    struct Node* res = NULL;

    struct Node* a = NULL;

    struct Node* b = NULL;

  

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

      функции

       Созданные списки, a: 5-> 10-> 15, b: 2-> 3-> 20 * /

    push(&a, 15);

    push(&a, 10);

    push(&a, 5);

  

    push(&b, 20);

    push(&b, 3);

    push(&b, 2);

  

    / * Удалить дубликаты из связанного списка * /

    res = SortedMerge(a, b);

  

    printf("Merged Linked List is: \n");

    printList(res);

  

    return 0;

}

Джава

/ * Java-программа для объединения двух

   отсортированные связанные списки * /

import java.util.*;

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

class Node 

{

    int data;

    Node next;

    Node(int d) {data = d;

                 next = null;}

}

      

class MergeLists 

{
Node head; 

  
/ * Метод для вставки узла в

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

public void addToTheLast(Node node) 

{

    if (head == null)

    {

        head = node;

    }

    else 

    {

        Node temp = head;

        while (temp.next != null)

            temp = temp.next;

        temp.next = node;

    }

}

  
/ * Способ печати связанного списка * /

void printList()

{

    Node temp = head;

    while (temp != null)

    {

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

        temp = temp.next;

    

    System.out.println();

}

  

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

public static void main(String args[])

{

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

       списки для тестирования методов

       Созданные списки:

           llist1: 5-> 10-> 15,

           llist2: 2-> 3-> 20

    * /

    MergeLists llist1 = new MergeLists();

    MergeLists llist2 = new MergeLists();

      

    // Node head1 = new Node (5);

    llist1.addToTheLast(new Node(5));

    llist1.addToTheLast(new Node(10));

    llist1.addToTheLast(new Node(15));

      

    // Node head2 = new Node (2);

    llist2.addToTheLast(new Node(2));

    llist2.addToTheLast(new Node(3));

    llist2.addToTheLast(new Node(20));

      

      

    llist1.head = new Gfg().sortedMerge(llist1.head, 

                                        llist2.head);

    llist1.printList();     

      
}
}

  

class Gfg

{
/ * Принимает два списка, отсортированных в
увеличение порядка и сращивания
их узлы вместе, чтобы сделать
один большой отсортированный список, который
вернулся. * /
Node sortedMerge(Node headA, Node headB)
{

      

    / * фиктивный первый узел

       повесить результат на * /

    Node dummyNode = new Node(0);

      

    / * хвост указывает на

    последний результат узла * /

    Node tail = dummyNode;

    while(true

    {

          

        / * если какой-либо список исчерпан,

        используйте другой список * /

        if(headA == null)

        {

            tail.next = headB;

            break;

        }

        if(headB == null)

        {

            tail.next = headA;

            break;

        }

          

        / * Сравните данные двух

        списки, какие бы ни были данные списков

        поменьше, добавить его в хвост и

        продвинуть голову к следующему узлу

        * /

        if(headA.data <= headB.data)

        {

            tail.next = headA;

            headA = headA.next;

        

        else

        {

            tail.next = headB;

            headB = headB.next;

        }

          

        / * Продвигать хвост * /

        tail = tail.next;

    }

    return dummyNode.next;

}
}

  
// Этот код добавлен
// Шубхоу Кумар

C #

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

using System;

  

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

    public class Node 

    

        public int data; 

        public Node next; 

        public Node(int d) 

        {

            data = d; 

            next = null;

        

    

  

    public class MergeLists 

    

        Node head; 

  

        / * Метод для вставки узла в

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

        public void addToTheLast(Node node) 

        

            if (head == null

            

                head = node; 

            

            else

            

                Node temp = head; 

                while (temp.next != null

                    temp = temp.next; 

                temp.next = node; 

            

        

  

        / * Способ печати связанного списка * /

        void printList() 

        

            Node temp = head; 

            while (temp != null

            

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

                temp = temp.next; 

            

            Console.WriteLine(); 

        

  

  

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

        public static void Main(String []args) 

        

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

            списки для тестирования методов

            Созданные списки:

                   llist1: 5-> 10-> 15,

                llist2: 2-> 3-> 20

            * /

            MergeLists llist1 = new MergeLists(); 

            MergeLists llist2 = new MergeLists(); 

  

            // Node head1 = new Node (5);

            llist1.addToTheLast(new Node(5)); 

            llist1.addToTheLast(new Node(10)); 

            llist1.addToTheLast(new Node(15)); 

  

            // Node head2 = new Node (2);

            llist2.addToTheLast(new Node(2)); 

            llist2.addToTheLast(new Node(3)); 

            llist2.addToTheLast(new Node(20)); 

  

  

            llist1.head = new Gfg().sortedMerge(llist1.head, 

                                            llist2.head); 

            llist1.printList(); 

  

        

    

  

    public class Gfg 

    

    / * Принимает два списка, отсортированных в

    увеличение порядка и сращивания

    их узлы вместе, чтобы сделать

    один большой отсортированный список, который

    вернулся. * /

    public Node sortedMerge(Node headA, Node headB) 

    

  

        / * фиктивный первый узел

        повесить результат на * /

        Node dummyNode = new Node(0); 

  

        / * хвост указывает на

        последний результат узла * /

        Node tail = dummyNode; 

        while(true

        

  

            / * если какой-либо список исчерпан,

            используйте другой список * /

            if(headA == null

            

                tail.next = headB; 

                break

            

            if(headB == null

            

                tail.next = headA; 

                break

            

  

            / * Сравните данные двух

            списки, какие бы ни были данные списков

            поменьше, добавить его в хвост и

            продвинуть голову к следующему узлу

            * /

            if(headA.data <= headB.data) 

            

                tail.next = headA; 

                headA = headA.next; 

            

            else

            

                tail.next = headB; 

                headB = headB.next; 

            

  

            / * Продвигать хвост * /

            tail = tail.next; 

        

        return dummyNode.next; 

    

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

Выход :

Merged Linked List is: 
2 3 5 10 15 20 

Способ 2 (с использованием локальных ссылок)
Это решение структурно очень похоже на вышеприведенное, но оно избегает использования фиктивного узла. Вместо этого он поддерживает указатель структуры узла **, lastPtrRef, который всегда указывает на последний указатель списка результатов. Это решает тот же случай, что и фиктивный узел — работа со списком результатов, когда он пуст. Если вы пытаетесь создать список в его хвосте, можно использовать фиктивный узел или стратегию «ссылка» ** на узел структуры (подробности см. В разделе 1).

C ++

Node* SortedMerge(Node* a, Node* b) 

Node* result = NULL; 

      
/ * указатель на последний указатель результата * /
Node** lastPtrRef = &result; 

      

while(1) 

    if (a == NULL) 

    

    *lastPtrRef = b; 

    break

    

    else if (b==NULL) 

    

    *lastPtrRef = a; 

    break

    

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

    

    MoveNode(lastPtrRef, &a); 

    

    else

    

    MoveNode(lastPtrRef, &b); 

    

      

    / * хитроумно: перейти к следующему полю «.next» * /

    lastPtrRef = &((*lastPtrRef)->next); 

return(result); 

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

С

struct Node* SortedMerge(struct Node* a, struct Node* b) 

{

  struct Node* result = NULL;

    

  / * указатель на последний указатель результата * /

  struct Node** lastPtrRef = &result; 

    

  while(1) 

  {

    if (a == NULL) 

    {

      *lastPtrRef = b;

       break;

    }

    else if (b==NULL) 

    {

       *lastPtrRef = a;

       break;

    }

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

    {

      MoveNode(lastPtrRef, &a);

    }

    else 

    {

      MoveNode(lastPtrRef, &b);

    }

    

    / * хитроумно: перейти к следующему полю «.next» * /

    lastPtrRef = &((*lastPtrRef)->next); 

  }

  return(result);

}

Метод 3 (Использование рекурсии)
Слияние — одна из тех хороших рекурсивных проблем, где код рекурсивного решения намного чище, чем итеративный код. Однако вы, вероятно, не захотите использовать рекурсивную версию для производственного кода, поскольку она будет использовать пространство стека, пропорциональное длине списков.

C ++

Node* SortedMerge(Node* a, Node* b) 

    Node* result = NULL; 

      

    / * Базовые случаи * /

    if (a == NULL) 

        return(b); 

    else if (b == NULL) 

        return(a); 

      

    / * Выберите a или b и повторите * /

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

    

        result = a; 

        result->next = SortedMerge(a->next, b); 

    

    else

    

        result = b; 

        result->next = SortedMerge(a, b->next); 

    

    return(result); 

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

С

struct Node* SortedMerge(struct Node* a, struct Node* b) 

{

  struct Node* result = NULL;

  

  / * Базовые случаи * /

  if (a == NULL) 

     return(b);

  else if (b==NULL) 

     return(a);

  

  / * Выберите a или b и повторите * /

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

  {

     result = a;

     result->next = SortedMerge(a->next, b);

  }

  else 

  {

     result = b;

     result->next = SortedMerge(a, b->next);

  }

  return(result);

}

Джава

class GFG 

{

    public Node SortedMerge(Node A, Node B) 

    {

      

        if(A == null) return B;

        if(B == null) return A;

          

        if(A.data < B.data) 

        {

            A.next = SortedMerge(A.next, B);

            return A;

        }

        else 

        {

            B.next = SortedMerge(A, B.next);

            return B;

        }

          

    }

}

  
// Этот код предоставлен Tuhin Das

python3

# Программа Python3 объединяет две отсортированные ссылки
# в третьем связанном списке с использованием рекурсии.

  
# Класс узла

class Node:

    def __init__(self, data):

        self.data = data

        self.next = None

  

  
# Конструктор для инициализации объекта узла

class LinkedList:

  

    # Функция для инициализации головы

    def __init__(self):

        self.head = None

  

    # Способ печати связанного списка

    def printList(self):

        temp = self.head

          

        while temp :

            print(temp.data, end="->")

            temp = temp.next

  

    # Функция добавления узла в конце.

    def append(self, new_data):

        new_node = Node(new_data)

          

        if self.head is None:

            self.head = new_node

            return

        last = self.head

          

        while last.next:

            last = last.next

        last.next = new_node

  

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

def mergeLists(head1, head2):

  

    # создать временный узел NULL

    temp = None

  

    # List1 пуст, затем вернуть List2

    if head1 is None:

        return head2

  

    # если List2 пуст, то вернуть List1

    if head2 is None:

        return head1

  

    # Если данные List1 меньше или

    # равно данным List2

    if head1.data <= head2.data:

  

        # назначить временную привязку для данных List1

        temp = head1

  

        # Еще раз проверьте данные List1 меньше или равны List2

        # data и вызов функции mergeLists.

        temp.next = mergeLists(head1.next, head2)

          

    else:

        # Если данные List2 больше или равны List1

        # данные назначают температуру для head2

        temp = head2

  

        # Еще раз проверьте, что данные List2 больше или равны

        # data и вызов функции mergeLists.

        temp.next = mergeLists(head1, head2.next)

  

    # вернуть временный список.

    return temp

  

  
# Функция драйвера

if __name__ == '__main__':

  

    # Создать связанный список:

    # 10-> 20-> 30-> 40-> 50

    list1 = LinkedList()

    list1.append(10)

    list1.append(20)

    list1.append(30)

    list1.append(40)

    list1.append(50)

  

    # Создать связанный список 2:

    # 5-> 15-> 18-> 35-> 60

    list2 = LinkedList()

    list2.append(5)

    list2.append(15)

    list2.append(18)

    list2.append(35)

    list2.append(60)

  

    # Создать связанный список 3

    list3 = LinkedList()

  

    # Объединение связанного списка 1 и связанного списка 2

    # в связанном списке 3

    list3.head = mergeLists(list1.head, list2.head)

  

    print(" Merged Linked List is : ", end="")

    list3.printList()     

  

  
# Этот код предоставлен Shriaknt13.

Пожалуйста, обратитесь к посту ниже для более простых реализаций:
Объединить два отсортированных списка (на месте)

Источник: http://cslibrary.stanford.edu/105/LinkedListProblems.pdf

Пожалуйста, пишите комментарии, если вы обнаружите, что приведенный выше код / алгоритм неверен, или найдете лучшие способы решения той же проблемы.

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

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

0.00 (0%) 0 votes