Решение задачи #21. Python LeetCode, Merge two sorted lists

Задача на работу со связными списками и указателями.

Вариант решения задачи на Python с LeetCode

Категория: Алгоритмы.
Название задачи: Merge two sorted lists.
Сложность: Легкая.
Статус решения: "Решено".

Условие задачи:
Даны головы двух отсортированных связных списков list1 и list2. Объедините эти два списка в один отсортированный список. Новый список должен быть составлен путем соединения узлов исходных списков (без создания новых узлов). Верните голову объединенного связного списка.

Примечания:
Оба списка list1 и list2 уже отсортированы в порядке неубывания. Нельзя создавать новые узлы, нужно только переставлять указатели next существующих узлов.

Решение:

Python

# Определение узла связного списка
class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val    # Значение узла
        self.next = next  # Ссылка на следующий узел

class Solution(object):
    def mergeTwoLists(self, list1, list2):
        """
        Объединяет два отсортированных связных списка в один отсортированный список.
        
        Аргументы:
            list1: Голова первого связного списка
            list2: Голова второго связного списка
            
        Возвращает:
            Голову объединенного отсортированного связного списка
        """
        # Создаем фиктивный узел для упрощения кода
        dummy = ListNode(-1)
        # Указатель для построения нового списка
        current = dummy
        
        # Пока в обоих списках есть элементы
        while list1 is not None and list2 is not None:
            # Сравниваем значения текущих узлов
            if list1.val <= list2.val:
                current.next = list1  # Добавляем узел из list1
                list1 = list1.next    # Перемещаем указатель list1
            else:
                current.next = list2  # Добавляем узел из list2
                list2 = list2.next    # Перемещаем указатель list2
            current = current.next   # Перемещаем указатель current
        
        # Добавляем оставшиеся элементы из list1 или list2
        if list1 is not None:
            current.next = list1
        else:
            current.next = list2
        
        # Возвращаем голову нового списка (пропускаем фиктивный узел)
        return dummy.next

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

Источник решения: hdhai.com