题目要求
合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
解题思路
和合并两个排序链表的基本方式一样,通过递归,进行数组内的链表两两合并,是分治法的一种体现
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def mergeKLists(self, lists):
length = len(lists)
if length == 0:
return None
if length == 1:
return lists[0]
if length == 2:
return self.mergeParts(lists[0], lists[1])
mid = int(length/2)
left = self.mergeKLists(lists[0:mid])
right = self.mergeKLists(lists[mid:length])
return self.mergeParts(left, right)
def mergeParts(self, l1, l2):
head = ListNode(0)
tmp = head
while l1 and l2:
if l1.val < l2.val:
tmp.next = l1
l1 = l1.next
else:
tmp.next = l2
l2 = l2.next
tmp = tmp.next
if not l1:
tmp.next = l2
if not l2:
tmp.next = l1
return head.next