В этом посте я расскажу о решении проблемы leetcode - Объединить два отсортированных списка.
Проблема:
Объедините два отсортированных связанных списка и верните их как отсортированный список. Список должен быть составлен путем объединения узлов первых двух списков.
Пример 1:
Input: l1 = [1,2,4], l2 = [1,3,4] Output: [1,1,2,3,4,4]
Пример 2:
Input: l1 = [], l2 = [] Output: []
Пример 3:
Input: l1 = [], l2 = [0] Output: [0]
Ограничения:
- Количество узлов в обоих списках находится в диапазоне
[0, 50]
. -100 <= Node.val <= 100
- И
l1
, иl2
отсортированы в неубывающем порядке.
Решение:
Идея проста. Нам нужно выполнить итерацию по обоим спискам одновременно и создать еще один список, состоящий из узлов из обоих входных списков. Единственная загвоздка - решить, из какого списка выбрать узел.
- Создайте пустой узел и назовите его
tempNode
- Создайте еще один узел с именем
output
и назначьте емуtempNode
- Перебирайте оба списка
l1
иl2
, пока один из них или оба не будут полностью пройдены. - Во время итерации, если узел из
l1
имеет меньшее значение, чем узел изl2
, тогда назначьтеnext
oftempNode
l1
и переместитеl1
вперед. - В противном случае присвойте
next
oftempNode
l2
и переместитеl2
вперед. - На каждой итерации не забывайте продвигать
tempNode
, который содержит наш окончательный результат. - После цикла мы либо просматриваем оба входных списка, либо один из них. Поэтому проверьте, какой из них пройден, и назначьте другой
next
oftempNode
- Поскольку
output
был назначен пустому узлу, фактический список вывода начинается с output.next и, следовательно, возвращает его.
public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode tempNode = new ListNode(); ListNode output = tempNode; while(l1 != null && l2 != null) { if (l1.val < l2.val) { tempNode.next = l1; l1 = l1.next; } else { tempNode.next = l2; l2 = l2.next; } tempNode = tempNode.next; } tempNode.next = l1 == null ? l2 : l1; return output.next; }
Надеюсь это поможет! Удачного кодирования! 🙂
Если вы думаете, что решение можно улучшить или что-то упускает, не стесняйтесь комментировать. Всегда есть возможности для улучшения.
Найдите решения для проблем с leetcode здесь - https://github.com/rishikeshdhokare/leetcode-problems