Сложность: medium
Вам дан массив из k списков связанных списков, каждый связанный список отсортирован в порядке возрастания. Объедините все связанные списки в один отсортированный связанный список и верните его.
Пример:
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
👨💻 Алгоритм:
1️⃣Создаем новый связный список, который будет хранить объединенные узлы.
2️⃣В каждом проходе находим узел с наименьшим значением из всех первых узлов в списках и добавляем его в новый список.
3️⃣Повторяем процесс, пока все списки не будут объединены.
😎 Решение:
from typing import List, Optional
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
n = len(lists)
newList = ListNode()
new = newList
while n:
# Find list with smallest value
smallestNode = ListNode(float('inf'))
smallestIndex = -1
for i in range(n):
listNode = lists[i]
if listNode and listNode.val < smallestNode.val:
smallestNode = listNode
smallestIndex = i
if smallestIndex == -1:
break
new.next = ListNode(smallestNode.val)
new = new.next
if smallestNode.next:
lists[smallestIndex] = smallestNode.next
else:
lists.pop(smallestIndex)
n -= 1
return newList.next
Ставь 👍 и забирай 📚 Базу знаний