10044. LinkedList слияние
Произведите слияние двух отсортированных связных списков и
верните указатель на новый список. Новый список должен быть получен из двух
имеющихся в результате связывания их вершин при помощи указателей.
Определение связного списка:
//Java
class ListNode {
int
val;
ListNode next;
ListNode(int x) {
val =
x;
next
= null;
}
}
// C++
class ListNode
{
public:
int
val;
ListNode
*next;
ListNode(int x) : val(x), next(NULL) {}
};
Реализуйте функцию merge которая
сливает два связных списка.
// Java
ListNode merge(ListNode l1, ListNode
l2)
// C++
ListNode* merge(ListNode *l1,
ListNode *l2)
Пример
РЕШЕНИЕ
связный
список
Анализ алгоритма
Пусть res – указатель на результирующий
список. В конец res будем приписывать
вершину либо первого, либо второго списка (ту что меньше). Если первый список
закончится раньше, то к res припишем
то что останется от второго списка. Если второй список закончится раньше, то к res припишем то что останется от первого
списка.
Реализация алгоритма
ListNode* merge(ListNode *l1, ListNode *l2)
{
Создадим фиктивную вершину и
установим на нее текущий указатель current.
ListNode*
res = new ListNode(0);
ListNode*
current = res;
while (true)
{
Если список l1 закончился, то приписываем в конец current второй список l2.
if (l1 == NULL)
{
current->next = l2;
break;
}
Если список l2 закончился, то приписываем в конец current первый список l1.
if (l2 == NULL)
{
current->next
= l1;
break;
}
Если значение val первого списка меньше значения val второго списка, то к current приписываем вершину первого
списка.
if (l1->val < l2->val)
{
current->next = l1;
l1 =
l1->next;
}
Иначе к current приписываем вершину второго списка.
else
{
current->next = l2;
l2 = l2->next;
}
Продвигаемя по указателю current вперед.
current = current->next;
}
Возвращаем ответ, пропуская
первую фиктивную вершину.
return res->next;
}
Java реализация
ListNode merge(ListNode l1, ListNode l2)
{
ListNode res = new ListNode(0);
ListNode current = res;
while (true)
{
if (l1 == null)
{
current.next = l2;
break;
}
if (l2 == null)
{
current.next = l1;
break;
}
if (l1.val < l2.val)
{
current.next = l1;
l1 = l1.next;
}
else
{
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
return res.next;
}