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

Метод 1: итеративный подход
Итеративный подход включает в себя сравнение значений узлов из обоих связанных списков и создание нового объединенного списка путем связывания узлов в правильном порядке. Вот пример реализации на Python:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
def merge_lists_iterative(l1, l2):
    dummy = ListNode(0)
    current = dummy
    while l1 and l2:
        if l1.val < l2.val:
            current.next = l1
            l1 = l1.next
        else:
            current.next = l2
            l2 = l2.next
        current = current.next
    current.next = l1 if l1 else l2
    return dummy.next

Метод 2: рекурсивный подход
Рекурсивный подход использует концепцию объединения двух отсортированных списков. Мы рекурсивно объединяем более мелкие подзадачи, пока не достигнем базового случая. Вот пример реализации на Python:

def merge_lists_recursive(l1, l2):
    if not l1:
        return l2
    if not l2:
        return l1
    if l1.val < l2.val:
        l1.next = merge_lists_recursive(l1.next, l2)
        return l1
    else:
        l2.next = merge_lists_recursive(l1, l2.next)
        return l2

Метод 3: использование приоритетной очереди
Приоритетная очередь (минимальная куча) может использоваться для эффективного объединения отсортированных связанных списков. Мы помещаем головные узлы всех связанных списков в очередь приоритетов, а затем повторно извлекаем минимальный узел и добавляем его в объединенный список. Вот пример реализации на Python с использованием модуля heapq:

import heapq
def merge_lists_priority_queue(lists):
    dummy = ListNode(0)
    current = dummy
    heap = []
    for head in lists:
        if head:
            heapq.heappush(heap, (head.val, head))
    while heap:
        val, node = heapq.heappop(heap)
        current.next = node
        current = current.next
        if node.next:
            heapq.heappush(heap, (node.next.val, node.next))
    return dummy.next

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