Merge k Sorted Lists

1# Definition for singly-linked list.
2# class ListNode:
3#     def __init__(self, val=0, next=None):
4#         self.val = val
5#         self.next = next
6class Solution:
7    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
8        start = ListNode()
9        last = start
10        while True:
11            smallest_end = None
12            smallest_index = -1
13            for index, end in enumerate(lists):
14                if end is not None:
15                    if smallest_end is None:
16                        smallest_end = end
17                        smallest_index = index
18                    elif end.val < smallest_end.val:
19                        smallest_end = end
20                        smallest_index = index
21            
22            if smallest_end is None:
23                break
24            
25            last.next = ListNode(smallest_end.val)
26            last = last.next
27            lists[smallest_index] = lists[smallest_index].next
28        
29        return start.next
30            
31