Merge K Sorted Lists: the idea to remember.

The core insight

Keep each nonempty list head in a min heap. Append the smallest head and insert its successor.

Why it works

The smallest remaining node must be one of the current list frontiers, so extracting the smallest frontier is always safe.

The mistake to avoid

Use Integer.compare in the comparator to avoid overflow. This implementation relinks the original nodes.

Commented Java solution

Use java.util.* imports and a surrounding solution class. Tree snippets assume the standard TreeNode definition; linked lists use ListNode and Clone Graph uses a Node with val and neighbors; Copy Random List uses Node with val, next and random. Read the input assumptions above.

ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> Integer.compare(a.val, b.val));
    for (ListNode head : lists) if (head != null) heap.add(head);
    ListNode dummy = new ListNode(0), tail = dummy;
    while (!heap.isEmpty()) {
        ListNode node = heap.remove();
        if (node.next != null) heap.add(node.next);
        tail.next = node; tail = node;
    }
    return dummy.next;
}

Make the next connection