Даны два отсортированных связанных списка, состоящих из 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;
}