FastPrepMerge k Sorted Lists
Problem · Linked List

Merge k Sorted Lists

Learn this problem
● HardAmazon logoAmazonNEW GRADONSITE INTERVIEW
See Amazon hiring insights

Problem statement

You are given an array lists containing k linked-list heads. Every linked list is sorted in ascending order.

Merge all of the linked lists into one ascending linked list and return its head.

Function

mergeKLists(lists: ListNode[]) → ListNode

Examples

Example 1

lists = [[1,4,5],[1,3,4],[2,6]]return = [1,1,2,3,4,4,5,6]

The linked lists are:

1 -> 4 -> 5
1 -> 3 -> 4
2 -> 6

Merging them produces the sorted linked list 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6.

Example 2

lists = []return = []

Example 3

lists = [[]]return = []

Constraints

  • k == lists.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 10^4
  • Each lists[i] is sorted in ascending order.
  • The sum of all lists[i].length values does not exceed 10^4.

More Amazon problems

drafts saved locally
public ListNode mergeKLists(ListNode[] lists) {
    // write your code here
}
lists[[1,4,5],[1,3,4],[2,6]]
expected[1,1,2,3,4,4,5,6]
checking account