Day Nine

Today’s challenge was not simple, but I solved it with a simple method that might not be the best solution.

Problem description

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.

Examples

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

You can find a brief description about the problem here.

Experience

I first merged all the linked list elements into one list and sorted them. Then I formed a new linked list out of the sorted list.

The results

• Runtime: 135 ms, faster than 80.74% of SQL online submissions.
• Memory Usage: 18.3 MB, less than 28.93% of SQL online submissions.

The code

def mergeKLists(lists: List[Optional[ListNode]]) -> Optional[ListNode]:
	all_items = []
		
	for item in lists:
		while item:
			all_items.append(item.val)
		item = item.next
			
	if len(all_items) == 0: return None
		
	all_items.sort()
	new_sorted_list = ListNode(all_items[0])
	pointer = new_sorted_list
		
	for element in all_items[1:]:
		pointer.next = ListNode(element)
		pointer = pointer.next
		
	return new_sorted_list