Leetcode - Merge K Sorted Linked Lists

Question

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.

This is alinked_list question.

Idea

• Essentially using a merge sort algorithm (if we start with 4 lists, after the first merge, we’ll have 2 lists, then a single list (the solution)) This is an O(n*log(k)) solution.
• While lists > 1, establish mergedLists which are the lists we have merged
• Iterate through lists by each pair of lists (i and i+1), here we need to make sure i+1 is < len(lists), if i+1 is out of range, then list 2 is None
• Merge the two linked lists together and append to mergeLists using Leetcode - Merge Two Sorted Lists returning list 1 if list 2 is None
• When the while loop breaks, we will be left with one sorted linked list
• Return the last list

Solution