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

Постановка задачи

Даны два отсортированных связанных списка, и нам нужно объединить их вместе в один связанный список.

Кстати, связанный список — это еще одна структура данных, которая работает подобным образом.

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

Таким образом, технически вам предоставляются только главные узлы двух связанных списков. каждый узел имеет элемент данных (например, сообщение) и следующий элемент (указывающий на адрес другого узла)

Алгоритм

create a linked list and store the first node in ‘head’ variable
loop until one of the given nodes becomes null
    check which node has the smallest element
    create a node with the smallest value as data element
    assign the created node to the next element of list
    assign the current node the next node
if node of list 1 is not null
    then add all the nodes of list 1 to linked list
otherwise 
    add all the nodes of list 2 to the linked list

Решение на Питоне

class ListNode:
  def __init__(self, val=0, next=None):
    self.val = val
    self.next = next

class Solution:
  def __init__(self):
    self.result = ListNode()
    self.head = self.result

  def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:

    while list1 != None and list2 != None:
      if list1.val < list2.val:
        self.result.next = ListNode(list1.val)
        list1 = list1.next
      else:
        self.result.next = ListNode(list2.val)
        list2 = list2.next
      self.result = self.result.next

    if list1 == None:
      self.result.next = list2
    else:
      self.result.next = list1


    return self.head.next