> For the complete documentation index, see [llms.txt](https://mayanktyagi3111.gitbook.io/interview-prep/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mayanktyagi3111.gitbook.io/interview-prep/priority-queue/merge-k-sorted-lists.md).

# Merge k Sorted Lists

Merge *k* sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

**Example:**

```
Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6
```

```java
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
        // adding all the starting element from each list to PQ
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null) {
                pq.add(lists[i]);
            }
        }
        // Main work
        if (pq.peek() != null) {
            ListNode ans = new ListNode(0);
            ListNode ansPointer = ans;
            while (pq.size() != 0) {
                ListNode t = pq.poll();
                ansPointer.next = t;
                ansPointer = ansPointer.next;
                if (t.next != null) {
                    pq.add(t.next);
                }
            }
            return ans.next;
        } else {
            return null;
        }
    }
}
```