Объединить два отсортированных списка

Слияние двух отсортированных связанных списков — распространенная проблема на собеседованиях по алгоритмическому кодированию. Задача состоит в том, чтобы объединить два списка в один отсортированный список, сохранив порядок элементов. Хотя на первый взгляд проблема может показаться простой, для ее решения можно использовать несколько подходов, каждый из которых имеет свои компромиссы с точки зрения временной и пространственной сложности.

В этой статье мы рассмотрим различные подходы к решению проблемы слияния двух отсортированных связанных списков. На протяжении всей статьи мы будем давать подробное объяснение каждого подхода, а также анализ его временной и пространственной сложности.

Итак, без лишних слов приступим.

Постановка проблемы:

Вам даны главы двух отсортированных связанных списков list1 и list2.

Объедините два списка в один отсортированный список. Список должен быть составлен путем соединения узлов первых двух списков.

Возвращает заголовок объединенного связанного списка.

Подход 1: итеративное решение

1. Создайте фиктивный узел и указатель, который будет действовать как объединенный список.
2. Выполните итерацию по обоим входным спискам одновременно, сравнивая значения текущих узлов.
3. Добавьте меньшее значение в объединенный список, переместив соответствующий указатель вперед.
4. Продолжайте этот процесс, пока один из списков не достигнет своего конца (т. е. его значение не станет равным нулю).
5. Достигнув конца одного списка, добавьте все оставшиеся узлы из другого списка в объединенный список.
6. Наконец, верните объединенный список, обратившись к dummy.next, который указывает на заголовок объединенного списка.

// ES6 Arrow Function
const mergeTwoLists = (list1, list2) => {

    // dummy node and pointer 
    let dummy = new ListNode(0);
    let pointer = dummy;

    // compare values and add to the merged list
    while(list1 !== null && list2 !== null) {
        if(list1.val < list2.val) {
            pointer.next = list1;
            list1 = list1.next;
        } else {
            pointer.next = list2;
            list2 = list2.next;
        }

        pointer = pointer.next;
    }

    // Add remaining nodes
    pointer.next = list1 !== null ? list1 : list2;

    return dummy.next;
}

Временная сложность:O(N + M)

Мы перебираем оба списка один раз, и длина списков равна n и m соответственно. Таким образом, временная сложность линейно пропорциональна общему количеству узлов, присутствующих в списках.

Пространственная сложность:O(1)

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

Подход 2: рекурсивный

1. Базовый случай: если какой-либо из связанных списков пуст, вернуть другой список.
2. Сравните значения заголовков двух списков.
3. Установите меньшее значение в качестве заголовка объединенного списка.
4. Рекурсивно вызовите функцию со следующим узлом списка, имеющим меньшее значение.
5. Установите следующий указатель объединенного списка на результат рекурсивного вызова.
6. Вернуть объединенный список.

// ES6 Arrow Function
const 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), где N и M — длины двух входных связанных списков.

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

Пространственная сложность:O(N + M)

Рекурсивные вызовы используют стек вызовов, который увеличивается с количеством рекурсивных вызовов. В худшем случае, когда списки имеют одинаковую длину, максимальная глубина стека вызовов равна N (или M).

И у вас есть это, ребята! Мы изучили два разных подхода, увидели их реализацию в JavaScript и, надеюсь, повеселились. Я надеюсь, что эта статья предоставила вам ценную информацию и помогла лучше понять различные подходы к решению этой проблемы. Удачного кодирования!

Задача - Leetcode 21