Слияние отсортированных списков

Слияние двух отсортированных связных списков

Это классическая задача на работу со связными списками (linked lists). Требует понимания указателей и сравнения значений.

1. Определение структуры

from typing import Optional

class ListNode:
    def __init__(self, val: int = 0, next: Optional['ListNode'] = None):
        self.val = val
        self.next = next

2. Решение 1: Рекурсия (элегантно)

def merge_two_lists_recursive(list1: Optional[ListNode], 
                              list2: Optional[ListNode]) -> Optional[ListNode]:
    """Слияние двух отсортированных списков рекурсией."""
    
    # Базовые случаи
    if not list1:
        return list2
    if not list2:
        return list1
    
    # Рекурсивный случай: выбираем меньший элемент
    if list1.val <= list2.val:
        list1.next = merge_two_lists_recursive(list1.next, list2)
        return list1
    else:
        list2.next = merge_two_lists_recursive(list1, list2.next)
        return list2

Анализ:

• Время: O(n + m) где n и m — длины списков
• Память: O(n + m) стек рекурсии в худшем случае

3. Решение 2: Итеративное (оптимально)

def merge_two_lists_iterative(list1: Optional[ListNode], 
                               list2: Optional[ListNode]) -> Optional[ListNode]:
    """Слияние двух отсортированных списков итеративно."""
    
    # Создаём dummy узел для упрощения логики
    dummy = ListNode(0)
    current = dummy
    
    # Пока оба списка не пусты
    while list1 and list2:
        if list1.val <= list2.val:
            current.next = list1
            list1 = list1.next
        else:
            current.next = list2
            list2 = list2.next
        current = current.next
    
    # Присоединяем оставшейся список
    if list1:
        current.next = list1
    else:
        current.next = list2
    
    return dummy.next

Анализ:

• Время: O(n + m)
• Память: O(1) дополнительная

Почему используем dummy узел?

Без dummy:
- Нужно отдельно обрабатывать первый узел
- Код усложняется

С dummy:
- Всегда есть узел, к которому можно присоединить
- Упрощает логику
- dummy.next = результат

4. Визуализация работы

list1: 1 → 2 → 4
list2: 1 → 3 → 4

Шаг 0:
dummy(0) → current = dummy

Шаг 1: list1.val=1, list2.val=1
  1 <= 1 → выбираем list1
  dummy → 1
  current = список1[0], list1 = список1[1]

Шаг 2: list1.val=2, list2.val=1
  2 > 1 → выбираем list2
  dummy → 1 → 1
  current = список2[0], list2 = список2[1]

Шаг 3: list1.val=2, list2.val=3
  2 <= 3 → выбираем list1
  dummy → 1 → 1 → 2
  current = список1[1], list1 = список1[2]

Шаг 4: list1.val=4, list2.val=3
  4 > 3 → выбираем list2
  dummy → 1 → 1 → 2 → 3
  current = список2[1], list2 = список2[2]

Шаг 5: list1.val=4, list2.val=4
  4 <= 4 → выбираем list1
  dummy → 1 → 1 → 2 → 3 → 4
  current = список1[2], list1 = None

Шаг 6: list1 пуст, добавляем остаток list2
  dummy → 1 → 1 → 2 → 3 → 4 → 4

Результат: 1 → 1 → 2 → 3 → 4 → 4 ✓

5. Полная реализация с тестами

from typing import Optional
import unittest

class ListNode:
    def __init__(self, val: int = 0, next: Optional['ListNode'] = None):
        self.val = val
        self.next = next
    
    def to_list(self) -> list:
        """Конвертирует связный список в обычный список."""
        result = []
        current = self
        while current:
            result.append(current.val)
            current = current.next
        return result

class Solution:
    @staticmethod
    def merge_two_lists(list1: Optional[ListNode], 
                        list2: Optional[ListNode]) -> Optional[ListNode]:
        """Оптимальное решение: итеративное с dummy узлом."""
        dummy = ListNode(0)
        current = dummy
        
        while list1 and 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 if list1 else list2
        return dummy.next


class TestMergeTwoLists(unittest.TestCase):
    
    def _create_list(self, values: list) -> Optional[ListNode]:
        """Создаёт связный список из списка значений."""
        if not values:
            return None
        head = ListNode(values[0])
        current = head
        for val in values[1:]:
            current.next = ListNode(val)
            current = current.next
        return head
    
    def test_example_case(self):
        """Пример из задачи."""
        list1 = self._create_list([1, 2, 4])
        list2 = self._create_list([1, 3, 4])
        result = Solution.merge_two_lists(list1, list2)
        self.assertEqual(result.to_list(), [1, 1, 2, 3, 4, 4])
    
    def test_empty_lists(self):
        """Оба списка пусты."""
        result = Solution.merge_two_lists(None, None)
        self.assertIsNone(result)
    
    def test_one_empty_list(self):
        """Один список пуст."""
        list1 = self._create_list([1, 2, 3])
        result = Solution.merge_two_lists(list1, None)
        self.assertEqual(result.to_list(), [1, 2, 3])
        
        list2 = self._create_list([1, 2, 3])
        result = Solution.merge_two_lists(None, list2)
        self.assertEqual(result.to_list(), [1, 2, 3])
    
    def test_single_elements(self):
        """По одному элементу."""
        list1 = self._create_list([1])
        list2 = self._create_list([2])
        result = Solution.merge_two_lists(list1, list2)
        self.assertEqual(result.to_list(), [1, 2])
    
    def test_different_lengths(self):
        """Списки разной длины."""
        list1 = self._create_list([1, 5, 9])
        list2 = self._create_list([2, 3, 4, 6, 7, 8])
        result = Solution.merge_two_lists(list1, list2)
        self.assertEqual(result.to_list(), [1, 2, 3, 4, 5, 6, 7, 8, 9])
    
    def test_duplicate_values(self):
        """С дубликатами."""
        list1 = self._create_list([1, 2, 2])
        list2 = self._create_list([1, 2, 2])
        result = Solution.merge_two_lists(list1, list2)
        self.assertEqual(result.to_list(), [1, 1, 2, 2, 2, 2])

if __name__ == '__main__':
    unittest.main()

6. Альтернативное решение без dummy

def merge_two_lists_no_dummy(list1: Optional[ListNode], 
                              list2: Optional[ListNode]) -> Optional[ListNode]:
    """Слияние без dummy узла."""
    
    # Обработка граничных случаев
    if not list1:
        return list2
    if not list2:
        return list1
    
    # Определяем начальный узел
    if list1.val <= list2.val:
        head = list1
        list1 = list1.next
    else:
        head = list2
        list2 = list2.next
    
    current = head
    
    # Слияние остальных
    while list1 and 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 if list1 else list2
    return head

7. Сравнение подходов

8. Граничные случаи

# Случай 1: Оба пусты
merge(None, None) → None

# Случай 2: Один пуст
merge([1,2], None) → [1,2]

# Случай 3: Один элемент
merge([1], [2]) → [1,2]

# Случай 4: Все значения one list меньше
merge([1,2,3], [4,5,6]) → [1,2,3,4,5,6]

# Случай 5: Чередующиеся значения
merge([1,3,5], [2,4,6]) → [1,2,3,4,5,6]

9. Слияние k отсортированных списков

import heapq

def merge_k_lists(lists: list[Optional[ListNode]]) -> Optional[ListNode]:
    """Слияние k отсортированных списков (используя heap)."""
    
    # Min-heap: (value, list_index, node)
    heap = []
    
    # Инициализируем heap первыми элементами
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst.val, i, lst))
    
    dummy = ListNode(0)
    current = dummy
    
    while heap:
        val, idx, node = heapq.heappop(heap)
        current.next = node
        current = current.next
        
        if node.next:
            heapq.heappush(heap, (node.next.val, idx, node.next))
    
    return dummy.next

10. Сложность анализ

Итеративное решение:

Время:
- В худшем случае: O(n + m)
  где n = длина list1, m = длина list2
- Каждый узел посещается ровно один раз

Память:
- O(1) дополнительная память
- Создаём только dummy узел
- Переиспользуем исходные узлы

Структура результирующего списка:
- Использует узлы из обоих исходных списков
- Ничего не копируется

Вывод

Для слияния двух отсортированных списков:

1. Лучшее решение: Итеративное с dummy узлом
2. Почему dummy? Упрощает логику первого узла
3. Сложность: O(n + m) время, O(1) дополнительная память
4. Ключевая идея: Проходим оба списка, выбираем меньший элемент
5. Применение: Merge Sort для связных списков

Частая задача на собеседованиях — проверяет понимание связных списков и алгоритмических навыков.