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

Метод 1: итерация – обход и добавление

Один простой метод соединения двух связанных списков — это перебор первого списка до достижения его конца, а затем добавление заголовка второго списка к последнему узлу первого списка. Вот пример реализации на Python:

def connect_lists(list1, list2):
    current = list1
    while current.next:
        current = current.next
    current.next = list2
    return list1

Метод 2: рекурсивный подход

Другой подход к соединению двух связанных списков — использование рекурсивной функции. Функция будет рекурсивно проходить первый список, пока не достигнет конца, а затем прикрепит заголовок второго списка к последнему узлу первого списка. Вот пример реализации на Java:

public ListNode connectLists(ListNode list1, ListNode list2) {
    if (list1 == null) {
        return list2;
    }
    list1.next = connectLists(list1.next, list2);
    return list1;
}

Метод 3: изменение последнего узла

В этом методе мы изменяем последний узел первого связанного списка, чтобы он указывал на заголовок второго связанного списка. Этот подход позволяет избежать перебора первого связанного списка, что приводит к более эффективному решению. Вот пример реализации на C++:

void connectLists(Node* list1, Node* list2) {
    Node* current = list1;
    while (current->next != nullptr) {
        current = current->next;
    }
    current->next = list2;
}

Метод 4. Использование фиктивного узла

Для соединения двух связанных списков можно использовать фиктивный узел. Этот подход предполагает создание нового фиктивного узла и обновление его следующего указателя на заголовок первого списка. Затем мы проходим по первому списку до его конца и соединяем последний узел с заголовком второго списка. Вот пример реализации на C#:

public ListNode ConnectLists(ListNode list1, ListNode list2) {
    ListNode dummy = new ListNode(0);
    dummy.next = list1;
    ListNode current = dummy;
    while (current.next != null) {
        current = current.next;
    }
    current.next = list2;
    return dummy.next;
}

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