В этом посте я расскажу о решении проблемы 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 отсортированы в неубывающем порядке.

Решение:

Идея проста. Нам нужно выполнить итерацию по обоим спискам одновременно и создать еще один список, состоящий из узлов из обоих входных списков. Единственная загвоздка - решить, из какого списка выбрать узел.

  1. Создайте пустой узел и назовите его tempNode
  2. Создайте еще один узел с именем output и назначьте ему tempNode
  3. Перебирайте оба списка l1 и l2, пока один из них или оба не будут полностью пройдены.
  4. Во время итерации, если узел из l1 имеет меньшее значение, чем узел из l2, тогда назначьте nextof tempNode l1 и переместите l1 вперед.
  5. В противном случае присвойте nextof tempNode l2 и переместите l2 вперед.
  6. На каждой итерации не забывайте продвигать tempNode, который содержит наш окончательный результат.
  7. После цикла мы либо просматриваем оба входных списка, либо один из них. Поэтому проверьте, какой из них пройден, и назначьте другой nextof tempNode
  8. Поскольку 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