23. Merge k Sorted Lists

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 <= 10<sup>4</sup>

• 0 <= lists[i].length <= 500

• -10<sup>4</sup> <= lists[i][j] <= 10<sup>4</sup>

• lists[i] is sorted in ascending order.

• The sum of lists[i].length will not exceed 10<sup>4</sup>.

Initial Approach

So looking at the question we have to sort and merge the 2D array(not an array but just thinking in this way) / Linked List

• So first we make a empty linked list

• We have to add all the values to the empty linked list as they are different LL just like a list in a 2D array

• One thing we will use to iterate and add values while the other we will use to return the linked list as we have to return it from the start

So head.next will act as begin -> your LL

        head=tmp= ListNode()
        res=[]
        for l in lists:
            while l!=None:
                res.append(l.val)
                l=l.next
        for val in sorted(res):
            tmp.next=ListNode()
            tmp=tmp.next
            tmp.val=val
        return head.next

The above is the Code beats 78%

Time Complexity O(NlogN) as there is sorting :)

Space Complexity O(N)