[Linked List][Hard] 23. Merge k Sorted List

https://leetcode.com/problems/merge-k-sorted-lists/description

 

Q. k개의 정렬된 list 배열이 주어질 때, 이 모든 배열을 정렬된 상태로 하나의 리스트로 병합하여라. 

 

Solution.

 priority queue를 사용하면 간단한 문제. 

 

이를 이용해서 코드를 만들어 본다. 

 

 

C#

public ListNode MergeKLists(ListNode[] lists) 
{
    PriorityQueue<ListNode, int> pQ = new PriorityQueue<ListNode, int>();
    for(int q = 0; q < lists.Length; ++q)
    {
        if(lists[q] != null)
            pQ.Enqueue(lists[q], lists[q].val);
    }

    ListNode head = null;
    ListNode prev = null;
    while(pQ.Count > 0)
    {
        ListNode nodeQ = pQ.Peek();
        pQ.Dequeue();
        if(nodeQ == null)    break;

        ListNode node       = new ListNode(nodeQ.val);
        if(prev!=null)      prev.next = node;
        if(head == null)    head = node;

        prev = node;
        nodeQ = nodeQ.next;
        if(nodeQ != null)
            pQ.Enqueue(nodeQ, nodeQ.val);
    }
    return head;
}

 

적절한 결과를 얻었다. 

 

 

Note)

C#은 .NET 6.0 부터 priority queue가 생긴듯 하다. 

자주 쓰자.