Leetcode #06: „Обединяване на два сортирани списъка“

Свързаните списъци са основна структура от данни в компютърните науки, която се използва за съхраняване и манипулиране на колекции от данни. Те са полезни, когато размерът на колекцията не е известен предварително или когато се изисква динамично разпределение на паметта.

В тази статия ще проучим решение на проблема с Leetcode за сливане на два сортирани свързани списъка в Python. Ще обясним изложението на проблема, ще предоставим алгоритмично решение и ще включим Python код с коментари.

Постановка на проблема:

Дадени са заглавията на два сортирани свързани списъка, обединете двата списъка в един сортиран списък. Полученият списък трябва да бъде направен чрез снаждане на възлите на първите два списъка.

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Решение:

За да разрешим този проблем, можем да създадем нов свързан списък и да преминем през двата входни списъка, сравнявайки стойностите на техните възли и добавяйки по-малкия възел към новия списък. Можем да използваме два указателя, за да следим текущите възли във входните списъци, и трети указател, за да следим текущия възел в новия списък.

Можем да започнем, като създадем нов фиктивен възел, който ще бъде началният възел на обединения списък. След това можем да повторим двата входни списъка, като използваме цикъл while, който продължава, докато един от входните списъци бъде изчерпан.

Вътре в цикъла while можем да сравним стойностите на текущите възли във входните списъци. Ако стойността на възела в първия списък е по-малка, можем да го добавим към новия списък и да преместим показалеца към следващия възел в първия списък. Ако стойността на възела във втория списък е по-малка, можем да го добавим към новия списък и да преместим показалеца към следващия възел във втория списък.

След като цикълът while приключи, можем да проверим дали има останали възли в някой от списъците за въвеждане. Ако има, можем просто да ги добавим в края на новия списък.

Накрая можем да върнем началния възел на новия списък, който е следващият възел след фиктивния възел.

class Solution:
    def mergeTwoLists(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        # Create a dummy node and a reference to it for the current node
        dummy = cur = ListNode(0)
        
        # Continue the loop while both lists are not empty
        while l1 and l2:
            # Check which value is smaller between the two lists
            if l1.val < l2.val:
                # If the value from l1 is smaller, add it to the current node and move l1 to the next node
                cur.next = l1
                l1, cur = l1.next, cur.next
            else:
                # If the value from l2 is smaller, add it to the current node and move l2 to the next node
                cur.next = l2
                l2, cur = l2.next, cur.next
                
        # If either of the lists still has nodes, add them to the end of the merged list
        if l1:
            cur.next = l1
        if l2:
            cur.next = l2
            
        # Return the merged list, starting from the first node after the dummy node
        return dummy.next

Времева сложност:

Времевата сложност на този алгоритъм е O(m+n), където m и n са дължините на входните списъци. Това е така, защото трябва да повторим двата входни списъка веднъж, за да създадем обединения списък.

Космическа сложност:

Пространствената сложност на този алгоритъм е O(1), защото трябва само да създадем нов фиктивен възел и да използваме постоянно количество допълнителна памет, за да обединим входните списъци.

Заключение:

В тази статия проучихме решение на проблема с обединяването на два сортирани свързани списъка. Чрез създаване на нов свързан списък и итериране на входните списъци, можем да създадем единичен сортиран списък за O(m+n) време и O(1) пространство. Това решение е просто, ефективно и може да се приложи към различни проблеми със свързани списъци