> For the complete documentation index, see [llms.txt](https://shangan.gitbook.io/algorithm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://shangan.gitbook.io/algorithm/he-xin-suan-fa-200-ti/sort-algorithms/merge-k-sorted-lists.md).

# Merge k Sorted Lists

{% tabs %}
{% tab title="Java" %}

```java
//solution 1: PriorityQueue
class Solution {
		public ListNode mergeKLists(List<ListNode> lists) {
		ListNode dummy = new ListNode(-1);
		ListNode cur = dummy;
		PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> (a.val - b.val));
		for (ListNode head : lists) {
			if (head != null) {
				pq.offer(head);
			}
		}
		while (!pq.isEmpty()) {
			ListNode node = pq.poll();
			cur.next = node;
			if (node.next != null) {
				pq.offer(node.next);
			}
			cur = cur.next;
		}
		return dummy.next;
		}
}
Time Complexity : O(nlogk); //PriorityQueue
Space Complexity : O(n); //a new ListNode
```

{% endtab %}
{% endtabs %}