Grokking the Coding Interview: Patterns for Coding Questions

0% completed

​

Merge K Sorted Lists (medium)

Problem Statement

Given an array of ‘K’ sorted LinkedLists, merge them into one sorted list.

Example 1:

Input: L1=[2, 6, 8], L2=[3, 6, 7], L3=[1, 3, 4]
Output: [1, 2, 3, 3, 4, 6, 6, 7, 8]

Example 2:

Input: L1=[5, 8, 9], L2=[1, 7]
Output: [1, 5, 7, 8, 9]

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

Try it yourself

Try solving this question here:

.....

.....

.....

Like the course? Get enrolled and start learning!
S

saneer gera

· 4 years ago

this code is not working, how is it possible to compare value of two nodes?

Show 1 reply
C

Charlotte

· 4 years ago

How to do the question without defining an additional def lt(self, other): . In leetCode I'm not allowed to do that, but without that I cannot put nodes into the heap.

Show 3 replies
H

heena.sharma.iiitb

· 3 years ago

In the case of sorted lists, to merge them using a heap, I have to maintain a pointer to the list where the smaller element is being taken. In the case of LL it is simple to get the next element using a node.next, but how do we get the next element in the case of lists?

Bryan Le

Bryan Le

· a year ago

Class ListNode should be Node