Объединение двух отсортированных списков: разбор задачи

Почему эта задача важна?

Задача на объединение отсортированных списков позволяет оценить:

• 🧠 Понимание принципов работы с указателями и односвязными списками
• ⚡ Умение эффективно объединять упорядоченные данные
• 🎯 Навыки сохранения порядка и структуры при работе с данными
• 🔍 Способность обрабатывать разные краевые случаи

Постановка задачи

Формулировка:

Даны два отсортированных односвязных списка list1 и list2. Объедините их в один отсортированный список и верните его начало.

Примеры:

// Первый пример ✅
Input: list1 = [1, 2, 4], list2 = [1, 3, 5]
Output: [1, 1, 2, 3, 4, 5]

// Второй пример ✅
Input: list1 = [], list2 = []
Output: []

// Третий пример ✅
Input: list1 = [], list2 = [0]
Output: [0]

Ограничения:

• Длина каждого списка: 0 <= длина <= 100
• Значение узла: -100 <= Node.val <= 100
• Оба списка отсортированы в неубывающем порядке

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→

Подходы к решению

Решение 1: Итеративный подход 🔄

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
function mergeTwoLists(list1, list2) {
  // Создаем фиктивный узел, который будет началом результирующего списка
  const dummy = new ListNode(-1);
  let current = dummy;
  
  // Объединяем списки, пока оба не закончатся
  while (list1 !== null && list2 !== null) {
    if (list1.val <= list2.val) {
      current.next = list1;
      list1 = list1.next;
    } else {
      current.next = list2;
      list2 = list2.next;
    }
    current = current.next;
  }
  
  // Если один из списков закончился, добавляем оставшуюся часть другого
  if (list1 !== null) {
    current.next = list1;
  } else {
    current.next = list2;
  }
  
  // Возвращаем результат (пропуская фиктивный узел)
  return dummy.next;
}

Анализ решения:

✅ Оптимальная временная сложность O(n + m), где n и m - длины списков

✅ Пространственная сложность O(1) - не требует дополнительной памяти

✅ Понятная реализация с использованием фиктивного узла

✅ Эффективно работает с большими списками

Решение 2: Рекурсивный подход 🌲

function mergeTwoLists(list1, list2) {
  // Базовый случай: если один из списков пуст, возвращаем другой
  if (list1 === null) {
    return list2;
  }
  if (list2 === null) {
    return list1;
  }
  
  // Выбираем узел с меньшим значением и рекурсивно объединяем оставшуюся часть
  if (list1.val <= list2.val) {
    list1.next = mergeTwoLists(list1.next, list2);
    return list1;
  } else {
    list2.next = mergeTwoLists(list1, list2.next);
    return list2;
  }
}

Характеристики:

✅ Элегантная и компактная реализация

✅ Хорошо демонстрирует рекурсивный подход

❌ Пространственная сложность O(n + m) из-за стека вызовов

❌ Может вызвать переполнение стека для больших списков

Решение 3: Создание нового списка 🆕

function mergeTwoLists(list1, list2) {
  // Создаем фиктивный узел для результата
  const dummy = new ListNode(-1);
  let current = dummy;
  
  // Копии указателей для обхода исходных списков
  let p1 = list1;
  let p2 = list2;
  
  // Объединяем списки, создавая новые узлы
  while (p1 !== null && p2 !== null) {
    if (p1.val <= p2.val) {
      current.next = new ListNode(p1.val);
      p1 = p1.next;
    } else {
      current.next = new ListNode(p2.val);
      p2 = p2.next;
    }
    current = current.next;
  }
  
  // Добавляем оставшиеся элементы
  while (p1 !== null) {
    current.next = new ListNode(p1.val);
    p1 = p1.next;
    current = current.next;
  }
  
  while (p2 !== null) {
    current.next = new ListNode(p2.val);
    p2 = p2.next;
    current = current.next;
  }
  
  return dummy.next;
}

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

✅ Не изменяет исходные списки

✅ Подходит, если требуется сохранить оригинальные данные

❌ Требует дополнительной памяти O(n + m)

❌ Менее эффективен из-за создания новых узлов

Решение 4: Использование приоритетной очереди 📊

function mergeTwoLists(list1, list2) {
  // Для более общего случая (слияние k списков)
  // можно использовать приоритетную очередь
  
  // Создаем результирующий список
  const dummy = new ListNode(-1);
  let current = dummy;
  
  // Создаем массив для хранения текущих узлов из обоих списков
  const nodes = [];
  if (list1 !== null) nodes.push(list1);
  if (list2 !== null) nodes.push(list2);
  
  while (nodes.length > 0) {
    // Находим узел с минимальным значением
    let minIdx = 0;
    for (let i = 1; i < nodes.length; i++) {
      if (nodes[i].val < nodes[minIdx].val) {
        minIdx = i;
      }
    }
    
    // Добавляем минимальный узел в результат
    current.next = nodes[minIdx];
    current = current.next;
    
    // Обновляем массив узлов
    nodes[minIdx] = nodes[minIdx].next;
    if (nodes[minIdx] === null) {
      nodes.splice(minIdx, 1);
    }
  }
  
  return dummy.next;
}

Особенности:

✅ Обобщается на случай слияния k отсортированных списков

✅ Демонстрирует использование приоритетной очереди

❌ Избыточен для слияния всего двух списков

❌ Менее эффективен, чем прямое итеративное решение

Рекомендации по решению 💡

1. Выбор метода решения:

   • 🚀 Итеративный подход оптимален по памяти и простоте реализации
   • 📝 Рекурсивный подход элегантен для демонстрации понимания рекурсии
   • 🔍 Для собеседований важно уметь объяснить оба подхода

2. Важные моменты:

   • 📝 Обработка краевых случаев (пустые списки)
   • 🔄 Использование фиктивного узла для упрощения кода
   • 🧮 Правильное перемещение указателей

Распространённые ошибки

1. 🤦‍♂️ Забывание проверить пустые списки
2. 😅 Неправильное обновление указателей при объединении
3. 🐛 Потеря ссылки на начало результирующего списка

Оптимизации

Оптимизация с использованием деструктуризации (в языках, где это поддерживается)

function mergeTwoLists(list1, list2) {
  const dummy = new ListNode(-1);
  let current = dummy;
  
  while (list1 && list2) {
    if (list1.val <= list2.val) {
      [current.next, list1] = [list1, list1.next];
    } else {
      [current.next, list2] = [list2, list2.next];
    }
    current = current.next;
  }
  
  current.next = list1 || list2;
  
  return dummy.next;
}

Оптимизация рекурсивного решения для хвостовой рекурсии

function mergeTwoLists(list1, list2, merged = null, tail = null) {
  // Использование вспомогательной функции для хвостовой рекурсии
  function merge(l1, l2, mergedList, tailNode) {
    // Если оба списка пусты, возвращаем результат
    if (!l1 && !l2) return mergedList;
    
    // Если один из списков пуст
    if (!l1) {
      tailNode.next = l2;
      return mergedList;
    }
    if (!l2) {
      tailNode.next = l1;
      return mergedList;
    }
    
    // Выбираем меньший элемент
    if (l1.val <= l2.val) {
      tailNode.next = l1;
      return merge(l1.next, l2, mergedList, l1);
    } else {
      tailNode.next = l2;
      return merge(l1, l2.next, mergedList, l2);
    }
  }
  
  // Обработка краевых случаев
  if (!list1) return list2;
  if (!list2) return list1;
  
  // Инициализация результирующего списка
  const dummy = new ListNode(-1);
  
  return merge(list1, list2, dummy, dummy).next;
}

Визуализация процесса

Рассмотрим объединение списков [1, 2, 4] и [1, 3, 5]:

Начальное состояние:
list1: 1 -> 2 -> 4 -> null
list2: 1 -> 3 -> 5 -> null
result: dummy -> ?

Шаг 1: Сравниваем 1 и 1
list1: 1 -> 2 -> 4 -> null
list2: 1 -> 3 -> 5 -> null
result: dummy -> 1 -> ?

Шаг 2: Сравниваем 2 и 1
list1: 2 -> 4 -> null
list2: 1 -> 3 -> 5 -> null
result: dummy -> 1 -> 1 -> ?

Шаг 3: Сравниваем 2 и 3
list1: 2 -> 4 -> null
list2: 3 -> 5 -> null
result: dummy -> 1 -> 1 -> 2 -> ?

Шаг 4: Сравниваем 4 и 3
list1: 4 -> null
list2: 3 -> 5 -> null
result: dummy -> 1 -> 1 -> 2 -> 3 -> ?

Шаг 5: Сравниваем 4 и 5
list1: 4 -> null
list2: 5 -> null
result: dummy -> 1 -> 1 -> 2 -> 3 -> 4 -> ?

Шаг 6: Добавляем оставшийся элемент list2
list1: null
list2: 5 -> null
result: dummy -> 1 -> 1 -> 2 -> 3 -> 4 -> 5 -> null

Итоговый результат:
[1, 1, 2, 3, 4, 5]

Заключение

При решении задачи важно помнить:

• 🤹‍♂️ Существуют разные подходы, но итеративный обычно предпочтительнее по эффективности
• 📊 Использование фиктивного узла упрощает обработку краевых случаев
• 🧠 Важно правильно обрабатывать ситуации с пустыми списками

Эта задача является фундаментальной при работе со связными списками и демонстрирует важный алгоритмический паттерн слияния, который используется и в более сложных алгоритмах, таких как сортировка слиянием. 🌟