【LeetCode】23. Merge K ascending linked lists

1 subject

There are several points that need attention in this topic ：

• Because there are list The linked list in is empty , So you need to delete . But at the same time, because python There are some problems in deleting the list in , So we need to delete in reverse order list The content in .
• You should be proficient in the combination of linked lists . I think this topic should be very familiar , It must be no problem to do it directly , But it's better to write down the questions , It will be faster .

2 thought

This question is not a difficult one , Just a little trouble . It can be regarded as the multiple merging of two linked lists . The only thing is that the current linked list was generated last time .

3 Code

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
    def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
        for i in reversed(range(len(lists))):
            if lists[i] is None:
                del lists[i]
        # print(len(lists))

        if len(lists) == 0 or lists[0] is None:
            return None
        if len(lists) == 1:
            return lists[0]                        
        
        # print(head_1.val)
        #  If there are more than two linked lists 
        while(len(lists)>1):
            # merge
            head_1 = lists[0] #if len(lists[0]) else None
            head_2 = lists[1] #if len(lists[1]) else None #  The head node of the second linked list 
            if head_1.val <= head_2.val:
                head = head_1
                head_1 = head_1.next
            else:
                head = head_2
                head_2 = head_2.next
            tail = head # 

            while(head_1 and head_2):
                if head_1.val < head_2.val:                    
                    tail.next = head_1                    
                    head_1 = head_1.next
                else:                                        
                    tail.next = head_2
                    head_2 = head_2.next
                tail = tail.next
            
            #  Process remaining nodes 
            if head_1:
                tail.next = head_1
            if head_2:
                tail.next = head_2
            
            tmp = head
            # while(tmp):
            # print(tmp.val,end=",")
            # tmp = tmp.next
            # print("\n")
            lists[0] = head
            del lists[1]
            # print(len(lists))
            # break
        
        return head