Слияние двух отсортированных связанных списков

Даны два отсортированных связанных списка, состоящих из N и M узлов соответственно. Задача состоит в том, чтобы объединить оба списка (in-place) и вернуть главу объединенного списка.

Входные данные: Даны два списка из N и M узлов.
Однако количество узлов не является решающим фактором, операцию можно выполнить даже несмотря на измерение длины.

Подход

Оба списка отсортированы, хорошей идеей будет проверить, какой из 1-го узла в списке меньше, считайте, что переместили указатель, соответствующий меньшему узлу.

Пример продемонстрирован на следующем рисунке:

В конце концов, если есть оставшиеся узлы, мы просто добавляем их в список результатов.

Для вышеописанного подхода,
Временная сложность: O(min(n, m))
т.е. наименьшее количество перемещений связного списка.
Пространственная сложность: O(1)
т.е. не требуется дополнительного вспомогательного пространства, пропорционального входным данным.

Ниже приведены несколько вариантов реализации.

1. Java-реализация.

/*
  Merge two linked lists 
  head pointer input could be NULL as well for empty list
  Node is defined as 
    class Node
    {
        int data;
        Node next;
        Node(int d) {data = d; next = null; }
    }
*/

class LinkedList
{
    Node sortedMerge(Node head1, Node head2) {
     Node res = new Node(-1);
     Node itr = res;
     while(head1 != null && head2 != null) {
         if(head1.data <= head2.data) {
            itr.next = head1;
            head1 = head1.next;
         } else {
            itr.next = head2;
            head2 = head2.next;
         }
         itr = itr.next;
     }
     fillRest(head1, itr);
     fillRest(head2, itr);
     return res.next;
   } 

   void fillRest(Node head, Node itr) {
        if(head != null) 
            itr.next = head;
   }
}

Вход в полноэкранный режим Выход из полноэкранного режима

2. Реализация JavaScript / Node.js.


class Solution {
    fillRest(head, itr) {
        if(head !== null) 
            itr.next = head;
   }

    sortedMerge(head1, head2)
    {
        let res = new Node(-1);
        let itr = res;

        let getMin = () => {
            let min;
            if(head1.data <= head2.data) {
                min = head1;
                head1 = head1.next;
            } else {
                min = head2;
                head2 = head2.next;
            }
            return min;
        };

        while(head1 !== null && head2 !== null) {
             itr.next = getMin();
             itr = itr.next;
        }
         this.fillRest(head1, itr);
         this.fillRest(head2, itr);
         return res.next;
    }
}

Вход в полноэкранный режим Выход из полноэкранного режима

3. Реализация C++.


/* Link list Node
struct Node {
  int data;
  struct Node *next;

  Node(int x) {
    data = x;
    next = NULL;
  }
};
*/


//Function to merge two sorted linked list.
Node* sortedMerge(Node* head1, Node* head2)  
{  
    // code here
    Node res(-1);
     Node *itr = &res;

     auto fillRest = [] (Node* head, Node* itr) {
            if(head != NULL) 
                itr->next = head;
        };


     while(head1 != NULL && head2 != NULL) {
         if(head1 -> data <= head2 -> data) {
             itr-> next = head1;
             head1 = head1 -> next;
         } else {
             itr-> next = head2;
             head2 = head2 -> next;
         }
         itr = itr -> next;
     }

     fillRest(head1, itr);
     fillRest(head2, itr);
     return res.next;
}  

Вход в полноэкранный режим Выход из полноэкранного режима

Оцените статью
Procodings.ru
Добавить комментарий