[leetcode][23] Merge k Sorted Lists

[mylamour]

This is the common question of top100 from leetcode Merge k Sorted Lists

And since this issues, I would try to write my blog with english.

That's my solution, it's not elegant. Obviously, it can be solved with easy way by generate a new listnode

method 1

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

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        self.numbers = []
        self.head = self.tail = None
        
        for l in lists:
            if l:
                self.retrive(l)
        
        if not self.numbers:
            return None
        
        for item in sorted(self.numbers):
            self.add(item)
            
        return self.head
    
    def retrive(self, l):
        
        if l.next == None:
            self.numbers.append(l.val)
        else:
            self.numbers.append(l.val)
            self.retrive(l.next)
            
    def add(self, item):
    
        if not isinstance(item, ListNode):
            item = ListNode(item)

        if self.head is None:
            self.head = item
        else:
            self.tail.next = item

        self.tail = item

As you see, three functions consist of this class, retrive and add is main part to solve this problem, but it's not clearly.

method 1

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:

        self.nodes = []
        head = point = ListNode(0)
        for l in lists:
            while l:
                self.nodes.append(l.val)
                l = l.next
        for x in sorted(self.nodes):
            point.next = ListNode(x)
            point = point.next
        return head.next

well, it's look like better than we begin. but obviously, it's not the best one which we wanted. so, now we begin to learn another way to solve it.

method 2

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        amount = len(lists)
        interval = 1
        while interval < amount:
            for i in range(0, amount - interval, interval * 2):
                lists[i] = self.merge2Lists(lists[i], lists[i + interval])
            interval *= 2
        return lists[0] if amount > 0 else lists

    def merge2Lists(self, l1, l2):
        head = point = ListNode(0)
        while l1 and l2:
            if l1.val <= l2.val:
                point.next = l1
                l1 = l1.next
            else:
                point.next = l2
                l2 = l1
                l1 = point.next.next
            point = point.next
        if not l1:
            point.next=l2
        else:
            point.next=l1
        return head.next

But i am confused that this method is slowly than the method 1. at least in leetcode playgroud