Объясните пожалуйста работу этого кода?

Question

[Константин]

задача с leetcode - https://leetcode.com/problems/merge-two-sorted-lis...

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

Посмотрел решения и везде они +- одинаковые

решение

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        curr = dummy = ListNode()
        while l1 and l2:
            if l1.val >l2.val:
                curr.next = l2 
                l2 = l2.next 
            else:
                curr.next = l1
                l1 =l1.next 
            curr = curr.next 
        
        if not l1:
            curr.next =l2 

        else:
            curr.next = l1 
        return dummy.next

у меня несколько вопросов
1)curr = dummy = ListNode()
что это за конструкция. ну вернее я знаю, что это объект класса, но зачем сразу 2 переменные? сделал вот так
dummy = ListNode() и не работает
2)

if l1.val >l2.val:
                curr.next = l2 
                l2 = l2.next

объясните пожалуйста вот эти 2 строчки

curr.next = l2 
l2 = l2.next

3) Почему возвращаем именно dummy и next?
return dummy.next
Буду всем очень благодарен!

Answer 1

[Дмитрий Беляев]

1)curr = dummy = ListNode()
что это за конструкция. ну вернее я знаю, что это объект класса, но зачем сразу 2 переменные? сделал вот так
dummy = ListNode() и не работает

2 переменные нужны, что бы иметь ссылку и на начало и на конец списка, в конец будем добавлять ноды из других списков, а начало нужно чтоб потом сделать return

if l1.val >l2.val:
                curr.next = l2 
                l2 = l2.next

объясните пожалуйста вот эти 2 строчки

curr.next = l2 
l2 = l2.next

Через if выбрали из какого из 2 списков будем вставлять ноду в наш список и добавили ее туда, потом запомнили ссылку на следующую ноду выбранного списка

3) Почему возвращаем именно dummy и next?
return dummy.next

В dummy у нас начальная нода нашего списка, но она опорная, мы ее сами создали, а не взяли из исходных списков, а вот следующая - уже нода одного из списков.

Comments

[Константин]

Большое спасибо, у вас хорошее объяснение, я правда всё ещё немного не понимаю, но это уже дело практики)

Answer 2

[fenrir]

что это за конструкция. ну вернее я знаю, что это объект класса, но зачем сразу 2 переменные? сделал вот так

Два указателя на первый элемент списка чтобы не потерять начало. curr в процессе перемещается.

curr.next = l2 
l2 = l2.next

Привязываем минимальный элемент как следующий элемент нового списка, отвязываем от старого

Почему возвращаем именно dummy и next?

Потому что у нас первый элемент лежит в next, сам dummy это пустое начало нового списка

Я бы рекомендовал взять два списка с двумя-тремя элементами и пошагово посмотреть работу алгоритма или вообще нарисовать на бумаге, тогда все встанет на свои места.

Comments

[Константин]

Спасибо, согласен, что визуализировать код и эксперементировать с ним - это пожалуй лучше всего