23. 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

Merge two list

This problem rings a bell about a simpler version of the problem: merge 2 lists. We might need to use it later.

def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode

        """

        new_dummy_head = ListNode(1)
        cur_ptr = new_dummy_head

        while l1 and l2:
            if l1.val < l2.val:
                cur_ptr.next = l1
                l1 = l1.next
            else:
                cur_ptr.next = l2
                l2 = l2.next
            cur_ptr = cur_ptr.next

        if not l1:
            cur_ptr.next = l2
        if not l2:
            cur_ptr.next = l1

        return new_dummy_head.next


Combine one by one

We will call mergeTwoList k – 1 times and return the head.

    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        if not lists:
            return None
        if len(lists) == 1:
            return lists[0]

        dummy_head = lists[0]
        for i in range(1, len(lists)):
            dummy_head = self.mergeTwoLists(dummy_head, lists[i])

        return dummy_head

Space complexity

Since mergeTwoLists only alter next pointers of node, the space complexity is O(1).

Time complexity

Let the number of total node be N and the number of linked list be k.
We need to call mergeTwoList k – 1 times. And in the worst case, we need to traverse over the longer linked list of the two. Assuming the length of each linked list is equal, the longer linked list will have length of n / k, 2n / k … (k – 1)n/k. So the run time is
\sum_{i = 1}^{k - 1}{ \dfrac{N * i}{k}} = O(k^2 N)

Divide and conquer

Divide and conquer is a problem solving patterns that combine solutions of smaller instance to find the solution of the bigger problem.
In this problem, merge k linked list can become merging k // 2 linked lists who are the result of merging pairs of linked list.
from leetcode


def mergeKLists(self, lists): """ :type lists: List[ListNode] :rtype: ListNode """ if not lists: return None if len(lists) == 1: return lists[0] head_1 = self.mergeKLists(lists[:len(lists) // 2]) head_2 = self.mergeKLists(lists[len(lists) // 2:]) h = self.mergeTwoLists(head_1, head_2) return h

Run time

We have k linked list, so we will merge at most logk times. In the worst case scenario, the length of the longer linked list is O(n). So The run time is O(n log k).

Leave a Reply

Your email address will not be published. Required fields are marked *

To create code blocks or other preformatted text, indent by four spaces:

    This will be displayed in a monospaced font. The first four 
    spaces will be stripped off, but all other whitespace
    will be preserved.
    
    Markdown is turned off in code blocks:
     [This is not a link](http://example.com)

To create not a block, but an inline code span, use backticks:

Here is some inline `code`.

For more help see http://daringfireball.net/projects/markdown/syntax