23. Merge k Sorted Lists

public class Solution {
        public ListNode MergeKLists(ListNode[] lists)
        {            
            if (lists == null || lists.Length == 0)
                return null;
         
            return Merge(lists, 0, lists.Length - 1);
        }
        private ListNode Merge(ListNode[] lists, int i, int j)
        {
            if (j == i)
                return lists[i];
            else
            {
                int mid = i + (j - i) / 2;
                ListNode left = Merge(lists, i, mid),
                         right = Merge(lists, mid + 1, j);
                return Merge(left, right);
            }
        }
        private ListNode Merge(ListNode list1, ListNode list2)
        {
            ListNode dummy = new ListNode(0),
                     cur = dummy;
            while (list1 != null && list2 != null)
            {
                if (list1.val <= list2.val)
                {
                    cur.next = list1;
                    list1 = list1.next;
                }
                else
                {
                    cur.next = list2;
                    list2 = list2.next;
                }
                cur = cur.next;
            }
            if (list1 != null)
                cur.next = list1;
            if (list2 != null)
                cur.next = list2;
            return dummy.next;
        }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
        public ListNode MergeKLists(ListNode[] lists)
        {            
            if (lists == null || lists.size() == 0)
                return null;
         
            return Merge(lists, 0, lists.size() - 1);
        }
        private ListNode Merge(ListNode[] lists, int i, int j)
        {
            if (j == i)
                return lists[i];
            else
            {
                int mid = i + (j - i) / 2;
                ListNode left = Merge(lists, i, mid),
                         right = Merge(lists, mid + 1, j);
                return Merge(left, right);
            }
        }
        private ListNode Merge(ListNode list1, ListNode list2)
        {
            ListNode dummy = new ListNode(0),
                     cur = dummy;
            while (list1 != null && list2 != null)
            {
                if (list1.val <= list2.val)
                {
                    cur.next = list1;
                    list1 = list1.next;
                }
                else
                {
                    cur.next = list2;
                    list2 = list2.next;
                }
                cur = cur.next;
            }
            if (list1 != null)
                cur.next = list1;
            if (list2 != null)
                cur.next = list2;
            return dummy.next;
        }
}

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists.length==0) return null;
        Queue<ListNode> minHeap = new PriorityQueue<>((head1,head2)->head1.val-head2.val);
        for(ListNode listNode: lists){
            if(listNode!=null) minHeap.offer(listNode);
        }
        ListNode head=null,cur=null;
        while(!minHeap.isEmpty()){
            ListNode curNode = minHeap.poll();
            if(curNode.next!=null) minHeap.offer(curNode.next);
            if(head==null){
                head = new ListNode(curNode.val);
                cur = head;
            }
            else{
                cur.next = new ListNode(curNode.val);
                cur = cur.next;
            }
        }
        return head;
    }
}

/
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function (lists) {
    const pq = new MinPriorityQueue({ priority: node => node.val });
    for (const head of lists) {
        if (head) {
            pq.enqueue(head);
        }
    }
    const dummy = new ListNode();
    let cur = dummy;
    while (!pq.isEmpty()) {
        const node = pq.dequeue().element;
        cur.next = node;
        cur = cur.next;
        if (node.next) {
            pq.enqueue(node.next);
        }
    }
    return dummy.next;
};

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

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
}

Explanation

Данный код представляет собой класс `Solution`, в котором содержатся методы для объединения нескольких отсортированных списков в один общий отсортированный список. Давайте разберем пошагово, что происходит в каждом из методов:

1. Метод `MergeKLists` принимает массив списков `lists` и возвращает объединенный список. Если входной массив `lists` равен `null` или его длина равна 0, то метод вернет `null`. В противном случае метод вызывает вспомогательный метод `Merge`, передавая ему массив `lists`, начальный индекс 0 и конечный индекс `lists.Length - 1`.

2. В методе `Merge` осуществляется проверка условия, при котором начальный индекс `i` равен конечному индексу `j`. Если это условие выполняется, метод возвращает список из массива `lists` по индексу `i`. В противном случае происходит разбиение массива на две части посредством вычисления среднего индекса `mid`. Затем метод рекурсивно вызывает себя для левой половины массива и для правой половины массива, получая два подсписка `left` и `right`. Затем вызывается отдельный метод `Merge`, который объединяет два подсписка в один.

3. Метод `Merge` принимает два списка `list1` и `list2` и создает фиктивный узел `dummy`. При помощи указателя `cur` осуществляется сравнение элементов `val` двух списков и добавление их в новый список в отсортированном порядке. Таким образом, метод просматривает оба списка `list1` и `list2`, сравнивая и перенаправляя указатель на следующий минимальный элемент. П

осле окончания цикла, оставшиеся элементы списка добавляются в конец нового списка.

В итоге, данный код реализует эффективный способ объединения нескольких отсортированных списков в один общий отсортированный список, используя подход "разделяй и властвуй" и пространственную сложность O(1).