Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
Intuition & Algorithm
As for sorting, you can refer here for more about sorting algorithms.
Python
class Solution(object): def mergeKLists(self, lists): """ :type lists: List[ListNode] :rtype: ListNode """ self.nodes = [] head = point = ListNode(0) for l in lists: while l: self.nodes.append(l.val) l = l.next for x in sorted(self.nodes): point.next = ListNode(x) point = point.next return head.next
Complexity Analysis
Time complexity : where is the total number of nodes.
Space complexity : .
Algorithm
!?!../Documents/23_Merge_lists.json:1000,563!?!
Complexity Analysis
Time complexity : where is the number of linked lists.
Space complexity :
Algorithm
Almost the same as the one above but optimize the comparison process by priority queue. You can refer here for more information about it.
Python
from Queue import PriorityQueue class Solution(object): def mergeKLists(self, lists): """ :type lists: List[ListNode] :rtype: ListNode """ head = point = ListNode(0) q = PriorityQueue() for l in lists: if l: q.put((l.val, l)) while not q.empty(): val, node = q.get() point.next = ListNode(val) point = point.next node = node.next if node: q.put((node.val, node)) return head.next
Complexity Analysis
Time complexity : where is the number of linked lists.
Space complexity :
Algorithm
Convert merge lists problem to merge 2 lists () times. Here is the merge 2 lists problem page.
Complexity Analysis
Time complexity : where is the number of linked lists.
Space complexity :
Intuition & Algorithm
This approach walks alongside the one above but is improved a lot. We don't need to traverse most nodes many times repeatedly
Pair up lists and merge each pair.
After the first pairing, lists are merged into lists with average length, then , and so on.
Repeat this procedure until we get the final sorted linked list.
Thus, we'll traverse almost nodes per pairing and merging, and repeat this procedure about times.
Python
class Solution(object): def mergeKLists(self, lists): """ :type lists: List[ListNode] :rtype: ListNode """ amount = len(lists) interval = 1 while interval < amount: for i in range(0, amount - interval, interval * 2): lists[i] = self.merge2Lists(lists[i], lists[i + interval]) interval *= 2 return lists[0] if amount > 0 else lists def merge2Lists(self, l1, l2): head = point = ListNode(0) while l1 and l2: if l1.val <= l2.val: point.next = l1 l1 = l1.next else: point.next = l2 l2 = l1 l1 = point.next.next point = point.next if not l1: point.next=l2 else: point.next=l1 return head.next
Complexity Analysis
Time complexity : where is the number of linked lists.
Space complexity :
Analysis written by: @Hermann0