Привет и добро пожаловать. Это официально третий день серии прохождений по 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