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

Метод 1: итеративный подход
Один из самых простых методов объединения двух связанных списков — использование итеративного подхода. Вот пошаговое описание:

1. Создайте новый пустой связанный список для хранения объединенных элементов.
2. Пройдите по первому связанному списку и добавьте каждый элемент в новый список.
3. После прохождения первого списка установите последний узел нового списка так, чтобы он указывал на начало второго списка.
4. Объединенный список завершен и готов к использованию.

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

def merge_lists_iterative(list1, list2):
    if not list1:
        return list2
    if not list2:
        return list1

    merged_list = list1
    while list1.next:
        list1 = list1.next
    list1.next = list2
    return merged_list

Метод 2: рекурсивный подход
Другой подход к объединению связанных списков — рекурсия. Этот метод обеспечивает элегантное решение, разбивая проблему на более мелкие подзадачи. Вот как это работает:

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

Давайте посмотрим пример реализации на Java:

public ListNode mergeListsRecursive(ListNode list1, ListNode list2) {
    if (list1 == null) {
        return list2;
    }
    if (list2 == null) {
        return list1;
    }

    if (list1.val < list2.val) {
        list1.next = mergeListsRecursive(list1.next, list2);
        return list1;
    } else {
        list2.next = mergeListsRecursive(list1, list2.next);
        return list2;
    }
}

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

1. Создайте два указателя, по одному для каждого списка (назовем их «current1» и «current2»).
2. Просматривайте оба списка одновременно, сравнивая значения узлов.
3. При обнаружении меньшего значения соответствующим образом обновляйте указатели, чтобы сохранить порядок слияния.
4. Продолжайте этот процесс, пока один из списков не будет исчерпан.
5. Если в неисчерпанном списке присутствуют оставшиеся узлы, добавьте их в объединенный список.

Вот пример реализации на C++:

ListNode* mergeListsInPlace(ListNode* list1, ListNode* list2) {
    if (list1 == nullptr) {
        return list2;
    }
    if (list2 == nullptr) {
        return list1;
    }
    ListNode* head = nullptr;
    ListNode* current = nullptr;
    while (list1 != nullptr && list2 != nullptr) {
        if (list1->val < list2->val) {
            if (head == nullptr) {
                head = list1;
                current = head;
            } else {
                current->next = list1;
                current = current->next;
            }
            list1 = list1->next;
        } else {
            if (head == nullptr) {
                head = list2;
                current = head;
            } else {
                current->next = list2;
                current = current->next;
            }
            list2 = list2->next;
        }
    }
    if (list1 != nullptr) {
        current->next = list1;
    }
    if (list2 != nullptr) {
        current->next = list2;
    }
    return head;
}

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