23

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int val=0, ListNode next=null) {
 *         this.val = val;
 *         this.next = next;
 *     }
 * }
 */
 
 
 public class Solution {
    public ListNode MergeKLists(ListNode[] lists) {
        var pq = new PriorityQueue<ListNode, int>();
 
        foreach (var head in lists)
            if (head != null) pq.Enqueue(head, head.val);
 
        var dummy = new ListNode();
        var tail = dummy;
 
        while (pq.Count > 0) {
            var popped = pq.Dequeue();
            tail.next = popped;
            tail = popped;
 
            if (popped.next != null) pq.Enqueue(popped.next, popped.next.val);
        }
 
        return dummy.next;
    }
}

Idea is to have a min heap, and get first element (non null) from all linked lists. Now we pop, and add to our returning linked list. And, from the linked list we popped, we want to enqueue the next node onto our heap. Then we repeat again.

For the returning linked list, we use a ‘dummy’ node. The tail pointer moves forward adding all the nodes. The real values start from dummy.next. Dummy is there just to keep track of the starting of our linked list.

Dummy node gives tail a starting point, so the first node needs no special case. The real list starts at dummy.next.