You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.
Example 1:
Input: lists = [[1,4,5],[1,3,4],[2,6]]
Output: [1,1,2,3,4,4,5,6]
Explanation: The linked-lists are:
[
1->4->5,
1->3->4,
2->6
]
merging them into one sorted list:
1->1->2->3->4->4->5->6
Example 2:
Input: lists = []
Output: []
Example 3:
Input: lists = [[]]
Output: []
Constraints:
k == lists.length
0 <= k <= 104
0 <= lists[i].length <= 500
-104 <= lists[i][j] <= 104
lists[i] is sorted in ascending order.
The sum of lists[i].length will not exceed 104.
Solutions
Solution 1: Priority Queue (Min Heap)
We can create a min heap $pq$ to maintain the head nodes of all linked lists. Each time, we take out the node with the smallest value from the min heap, add it to the end of the result linked list, and then add the next node of this node to the heap. Repeat the above steps until the heap is empty.
The time complexity is $O(n \times \log k)$, and the space complexity is $O(k)$. Here, $n$ is the total number of all linked list nodes, and $k$ is the number of linked lists given in the problem.
1 2 3 4 5 6 7 8 9101112131415161718
# Definition for singly-linked list.# class ListNode:# def __init__(self, val=0, next=None):# self.val = val# self.next = nextclassSolution:defmergeKLists(self,lists:List[Optional[ListNode]])->Optional[ListNode]:setattr(ListNode,"__lt__",lambdaa,b:a.val<b.val)pq=[headforheadinlistsifhead]heapify(pq)dummy=cur=ListNode()whilepq:node=heappop(pq)ifnode.next:heappush(pq,node.next)cur.next=nodecur=cur.nextreturndummy.next
/** * Definition for singly-linked list. * type ListNode struct { * Val int * Next *ListNode * } */funcmergeKLists(lists[]*ListNode)*ListNode{pq:=hp{}for_,head:=rangelists{ifhead!=nil{pq=append(pq,head)}}heap.Init(&pq)dummy:=&ListNode{}cur:=dummyforlen(pq)>0{cur.Next=heap.Pop(&pq).(*ListNode)cur=cur.Nextifcur.Next!=nil{heap.Push(&pq,cur.Next)}}returndummy.Next}typehp[]*ListNodefunc(hhp)Len()int{returnlen(h)}func(hhp)Less(i,jint)bool{returnh[i].Val<h[j].Val}func(hhp)Swap(i,jint){h[i],h[j]=h[j],h[i]}func(h*hp)Push(vany){*h=append(*h,v.(*ListNode))}func(h*hp)Pop()any{a:=*h;v:=a[len(a)-1];*h=a[:len(a)-1];returnv}