【LeetCode】23. 合并K个升序链表

1 题目

本题有几个需要注意的地方：

• 因为有的list中的链表是空的，所以需要删除。但同时因为python 中的列表删除存在一定的问题，所以我们需要倒序删除list中的内容。
• 链表合并的题要熟练。我觉得这种题目要非常熟悉，直接做肯定是没问题的，但最好还是要记下题，这样会更快些。

2 思想

这题不是难题，只不过是稍有麻烦而已。可以看作是两个链表的多次合并。只不过是当前的一个链表是上次生成的。

3 代码

# 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)
        # 如果存在大于两条链表
        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 # 第二条链表的头结点
            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
            
            # 处理剩余节点
            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