LeetCode-23-合并K个升序链表

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。

image.png

解题思路：

1. 新建合并两个链表的函数；
2. 两两合并K个升序链表；
3. 合并两个链表的思路：初始化p和q同时指向list1和list2两个链表val小的那一个，然后同时遍历list1和list2，直至一个链表结束，再使p指向另一个未遍历完的链表。

Python3代码：

# 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[ListNode]) -> ListNode:
        if len(lists) == 0:
            return None
        if len(lists)==1 and not lists[0]:
            return None
        def merge(lists, start, end):
            if start==end: return lists[start]
            if start>end: return None
            mid = (start+end)//2
            return merge_two_list(merge(lists, start, mid), merge(lists, mid+1, end))

        def merge_two_list(list1, list2):
            if not list1 or not list2:
                return list1 if list1 else list2
            p1 = list1
            p2 = list2
            q = p = p1 if p1.val < p2.val else p2
            if p == p1: p1 = p1.next
            if p == p2: p2 = p2.next
            while p1 and p2:
                if p1.val < p2.val:
                    p.next = p1
                    p1 = p1.next
                else:
                    p.next = p2
                    p2 = p2.next
                p = p.next
            p.next = p1 if p1 else p2
            return q
        return merge(lists, 0, len(lists)-1)