23. Merge k Sorted Lists

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.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

'''
[1] sort)

idea::
1. while traversing all linked list, append val to list
2. sort it
3. make linked list using sorted list

code::
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    tmp=[]

    for l in lists:
        while l:
            tmp.append(l.val)
            l=l.next

    dummy=ListNode(-1,None)
    writer=dummy

    for val in sorted(tmp):
        writer.next=ListNode(val)
        writer=writer.next
    return dummy.next
    
-T/C: O(NlogN) # N==the number of all nodes
-S/C: O(N)
'''

'''
[2] k Pointers)

idea::
using k readers and 1 writer, compare k readers' val and link all

-T/C: O(kN) # k==the number of lists, # due to comparing and trversal
-S/C: O(1)
'''

'''
[3] merge-sort approach)

idea::
like merge-sort. it dosen't need to sort, so just merge.

code::
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
    if len(lists)==0:
        return None
    colabo=1
    while colabo<len(lists):
        for i in range(0,len(lists)-colabo,colabo*2):
            lists[i]=self.mergeTwoLists(lists[i],lists[i+colabo])
        colabo*=2
    return lists[0]



def mergeTwoLists(self, list1, list2):
    dummy=ListNode(-1,None)
    writer=dummy
    while list1 and list2:
        if list1.val>list2.val:
            writer.next=list2
            list2=list2.next
        elif list1.val==list2.val:
            writer.next=list1
            list1=list1.next
            writer=writer.next
            writer.next=list2
            list2=list2.next
        else:
            writer.next=list1
            list1=list1.next
        writer=writer.next
    if list1:
        writer.next=list1
    if list2:
        writer.next=list2
    return dummy.next
        
-T/C: O(Nlogk)
-S/C: O(1)
'''

class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        if len(lists)==0:
            return None
        colabo=1
        while colabo<len(lists):
            for i in range(0,len(lists)-colabo,colabo*2):
                lists[i]=self.mergeTwoLists(lists[i],lists[i+colabo])
            colabo*=2
        return lists[0]
        
            
    
    def mergeTwoLists(self, list1, list2):
        dummy=ListNode(-1,None)
        writer=dummy
        while list1 and list2:
            if list1.val>list2.val:
                writer.next=list2
                list2=list2.next
            elif list1.val==list2.val:
                writer.next=list1
                list1=list1.next
                writer=writer.next
                writer.next=list2
                list2=list2.next
            else:
                writer.next=list1
                list1=list1.next
            writer=writer.next
        if list1:
            writer.next=list1
        if list2:
            writer.next=list2
        return dummy.next