Flatten Linked List: задача на слияние K отсортированных списков

Flatten Linked List: как распознать слияние K отсортированных списков

Представьте: на собеседовании дают связный список с указателями next и bottom, все вертикальные списки уже отсортированы. Половина кандидатов начинает паниковать — а сильные сразу видят flatten linked list как задачу на слияние K отсортированных списков. Давайте научимся видеть этот паттерн.

Условие задачи flatten linked list

Дан связный список, где указатель next соединяет разные списки горизонтально, а bottom — узлы по вертикали. Каждый вертикальный список уже отсортирован. Нужно «сплющить» всю структуру в один отсортированный связный список, используя только указатель bottom.

Пример:

5 -> 10 -> 19 -> 28
|     |     |     |
7     20    22    35
|           |     |
8           50    40
|
30

Вывод:

5 -> 7 -> 8 -> 10 -> 19 -> 20 -> 22 -> 28 -> 30 -> 35 -> 40 -> 50

Наивный подход — и почему он не подходит

Первый интуитивный способ:

• Обойти все узлы
• Сохранить значения в массив
• Отсортировать массив
• Перестроить список заново

Вот реализация на Python:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.bottom = None

def flatten_brute(root):
    values = []
    current = root
    # Собираем все значения
    while current:
        temp = current
        while temp:
            values.append(temp.data)
            temp = temp.bottom
        current = current.next
    # Сортируем
    values.sort()
    # Перестраиваем список
    if not values:
        return None
    new_root = Node(values[0])
    curr = new_root
    for val in values[1:]:
        curr.bottom = Node(val)
        curr = curr.bottom
    return new_root

Сложность: O(N log N) по времени, O(N) по памяти, где N — общее количество узлов.

Проблема: мы игнорируем тот факт, что каждый вертикальный список уже отсортирован. А это ключевая подсказка.

Оптимальный подход — слияние отсортированных списков

Если в задаче есть несколько отсортированных списков и их нужно объединить в один — это классический паттерн Merge K Sorted Lists. Для flatten linked list мы применяем рекурсивное слияние справа налево.

Алгоритм flatten linked list

1. Рекурсивно сплющиваем правую часть: root.next = flatten(root.next)
2. Сливаем текущий вертикальный список с уже сплющенной правой частью: return merge(root, root.next)
3. В merge используем стандартную логику слияния двух отсортированных списков через указатель bottom

Реализация на Python:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        self.bottom = None

def merge(a, b):
    """Слияние двух отсортированных списков через bottom"""
    dummy = Node(0)
    current = dummy
    
    while a and b:
        if a.data <= b.data:
            current.bottom = a
            a = a.bottom
        else:
            current.bottom = b
            b = b.bottom
        current = current.bottom
        current.next = None  # Обнуляем next, чтобы не было циклов
    
    if a:
        current.bottom = a
    else:
        current.bottom = b
    
    return dummy.bottom

def flatten(root):
    """Основная функция flatten linked list"""
    if root is None or root.next is None:
        return root
    
    # Рекурсивно сплющиваем правую часть
    root.next = flatten(root.next)
    
    # Сливаем текущий список с правой частью
    return merge(root, root.next)

Разбор на примере

Пусть вход:

5 -> 10 -> 19
|     |     |
7     20    22
|           |
8           50
|
30

Шаг 1: Сливаем 10 -> 20 и 19 -> 22 -> 50:
Результат: 10 -> 19 -> 20 -> 22 -> 50

Шаг 2: Сливаем 5 -> 7 -> 8 -> 30 и 10 -> 19 -> 20 -> 22 -> 50:
Результат: 5 -> 7 -> 8 -> 10 -> 19 -> 20 -> 22 -> 30 -> 50

Анализ сложности

Пусть N — общее количество узлов, K — количество вертикальных списков.

• Время: O(N × K) в худшем случае, так как каждый элемент может участвовать в нескольких слияниях
• Память: O(K) — глубина рекурсии

Почему это работает

Рекурсия гарантирует, что flatten(root.next) всегда возвращает отсортированный сплющенный список. После этого задача сводится к слиянию двух отсортированных списков — стандартной операции, которую вы уже знаете.

Ключевой инсайт: flatten linked list — это не новая задача, а знакомая Merge K Sorted Lists в disguise.

Практический вывод

Когда на собеседовании видите сложную структуру с несколькими отсортированными подсписками — ищите паттерн слияния. Прямо сейчас: откройте LeetCode, найдите задачу «Flatten a Multilevel Doubly Linked List» и решите её этим методом. Затем попробуйте задачу «Merge k Sorted Lists» — вы увидите, что техника та же.