题目链接：https://leetcode-cn.com/problems/merge-k-sorted-lists/
难度：困难

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

提示：
数组中的链表数：[0, 10000]
链表中的节点数：[0, 500]

题解

思路：
基本思想是先合并两个链表，在依次合并（不知道为什么超出时间限制，按理说复杂度也不高）或者归并合并。

  1. # Definition for singly-linked list.
  2. # class ListNode:
  3. #     def __init__(self, val=0, next=None):
  4. #         self.val = val
  5. #         self.next = next
  6. class Solution:
  7.     def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
  8.         if not lists:
  9.             return None
  10.         length = len(lists)
  11.         return self.merge(lists, 0, length-1)
  13.     def merge(self, lists, p, r):
  14.         if p == r:
  15.             return lists[p]
  16.         q = (p + r) // 2
  17.         l1 = self.merge(lists, p, q)
  18.         l2 = self.merge(lists, q+1, r)
  19.         return self.merge_two_list(l1, l2)
  21.     def merge_two_list(self, l1, l2):
  22.         if l1 is None:
  23.             return l2
  24.         if l2 is None:
  25.             return l1
  27.         dummy = ListNode()
  28.         cur = dummy
  29.         while l1 is not None and l2 is not None:
  30.             if l1.val < l2.val:
  31.                 cur.next = l1
  32.                 l1 = l1.next
  33.                 cur = cur.next
  34.             else:
  35.                 cur.next = l2
  36.                 l2 = l2.next
  37.                 cur = cur.next
  39.         cur.next = l1 if l1 is not None else l2
  40.         return dummy.next