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

Solution


Approach #1 Brute Force [Accepted]

Intuition & Algorithm

  • Traverse all the linked lists and collect the values of the nodes into an array.
  • Sort and iterate over this array to get the proper value of nodes.
  • Create a new sorted linked list and extend it with the new nodes.

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.

    • Collecting all the values costs time.
    • A stable sorting algorithm costs time.
    • Iterating for creating the linked list costs time.
  • Space complexity : .

    • Sorting cost space (depends on the algorithm you choose).
    • Creating a new linked list costs space.

Approach #2 Compare one by one [Accepted]

Algorithm

  • Compare every nodes (head of every linked list) and get the node with the smallest value.
  • Extend the final sorted linked list with the selected nodes.

!?!../Documents/23_Merge_lists.json:1000,563!?!

Complexity Analysis

  • Time complexity : where is the number of linked lists.

    • Almost every selection of node in final linked costs ( times comparison).
    • There are nodes in the final linked list.
  • Space complexity :

    • Creating a new linked list costs space.
    • It's not hard to apply in-place method - connect selected nodes instead of creating new nodes to fill the new linked list.

Approach #3 Optimize Approach 2 by Priority Queue [Accepted]

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.

    • The comparison cost will be reduced to for every pop and insertion to priority queue. But finding the node with the smallest value just costs time.
    • There are nodes in the final linked list.
  • Space complexity :

    • Creating a new linked list costs space.
    • The code above present applies in-place method which cost space. And the priority queue (often implemented with heaps) costs space (it's far less than in most situations).

Approach #4 Merge lists one by one [Accepted]

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.

    • We can merge two sorted linked list in time where is the total number of nodes in two lists.
    • Sum up the merge process and we can get: .
  • Space complexity :

    • We can merge two sorted linked list in space.

Approach #5 Merge with Divide And Conquer [Accepted]

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.

Divide_and_Conquer

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.

    • We can merge two sorted linked list in time where is the total number of nodes in two lists.
    • Sum up the merge process and we can get:
  • Space complexity :

    • We can merge two sorted linked lists in space.

Analysis written by: @Hermann0