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.

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.

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

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