Golang | LeetCode

Задача: 23. Merge k Sorted Lists #hard
Условие:

Вам дан массив из k списков связанных списков, каждый связанный список отсортирован в порядке возрастания.

Объедините все связанные списки в один отсортированный связанный список и верните его.

Решение:

import "container/heap"

type PQueue []*ListNode

func (pq PQueue) Len() int {
    return len(pq)
}

func (pq PQueue) Less(i, j int) bool {
    return pq[i].Val < pq[j].Val
}

func (pq PQueue) Swap(i, j int) {
  pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PQueue) Push(x interface{}) {
  item := x.(*ListNode)
  *pq = append(*pq, item)
}

func (pq *PQueue) Pop() interface{} {
  old := *pq
  n := len(old)
  item := old[n-1]
  old[n-1] = nil
  *pq = old[0 : n-1]
  return item
}

func (pq *PQueue) Peek(x interface{}) *ListNode {
    return (*pq)[len(*pq)-1]
}

func mergeKLists(lists []*ListNode) *ListNode {
    top := &ListNode{
        Val: -1,
    }
    merged := top
    pq := PQueue{}
    for _, l := range lists {
        if l != nil {
            pq = append(pq, l)
        }
    }
    heap.Init(&pq)
    for len(pq) > 0 {
        merged.Next = heap.Pop(&pq).(*ListNode)
        merged = merged.Next
        if merged.Next != nil {
            heap.Push(&pq, merged.Next)
        }
    }
    return top.Next
}

Пояснение:
Этот код реализует алгоритм слияния k отсортированных связанных списков.

В этом коде определен тип pqueue, который представляет очередь с приоритетами, основанную на куче. Каждый элемент в очереди представляет узел списка и содержит значение этого узла.

Методы len, less, swap определены для работы с очередью. Методы push и pop добавляют и удаляют элементы из очереди соответственно. Метод peek возвращает элемент с наивысшим приоритетом (с наименьшим значением) в очереди.

Функция mergeklists принимает массив lists содержащий указатели на начало каждого отсортированного связанного списка. Алгоритм начинает слияние, добавляя все не пустые списки в приоритетную очередь. Затем в цикле извлекается узел с наименьшим значением из очереди и добавляется к результату слияния. Если узел имеет следующий элемент, он добавляется обратно в очередь. Этот процесс продолжается, пока очередь не станет пустой.

В конце функция возвращает указатель на первый элемент нового отсортированного связанного списка.

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

👍2❤1

731 views15:06