Problem statement: Given an array of k sorted linked lists, your task is to merge them into a single sorted linked list and return the head of this linked list.

Recommended solution: Iteratively merge pairs of lists.

Time complexity: “The time complexity is O(nlogk), where k is the number of the lists and n is the maximum length of a single list.”

Should this be O(nklogk)? Take for example k = 8, n = 100. We’ll process all 800 elements a total of three times, meaning 100 * 8 * log8 = nklogk.

Course: Grokking Coding Interview Patterns in Python - Learn Interactively

Lesson: Solution: Merge K Sorted Lists