@author: ZZQ
@software: PyCharm
@file: mergeKLists.py
@time: 2018/10/12 19:55
说明:合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。
示例 :
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
思路:两两合并再合并,判断奇偶,每次用一个新的数组来存放当前经过合并后的新的链表首节点,时间复杂度:O(nlogn)
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def mergeTwoLists(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
if l1 is None and l2 is None:
return None
if l1 is None:
return l2
if l2 is None:
return l1
l3 = ListNode(0)
head = l3
while l1 is not None and l2 is not None:
if l1.val > l2.val:
l3.next = l2
l2 = l2.next
else:
l3.next = l1
l1 = l1.next
l3 = l3.next
if l1 is not None and l2 is None:
l3.next = l1
if l1 is None and l2 is not None:
l3.next = l2
return head.next
def mergeKLists(self, lists):
"""
:type lists: List[ListNode]
:rtype: ListNode
"""
if len(lists) == 0:
return None
cur_list = lists
while len(cur_list) > 1:
cur_temp_list = []
if len(cur_list) % 2:
for i in range((len(cur_list) - 1) / 2):
cur_temp_list.append(self.mergeTwoLists(cur_list[i * 2], cur_list[i * 2 + 1]))
cur_temp_list.append(cur_list[len(cur_list)-1])
else:
for i in range(len(cur_list) / 2):
cur_temp_list.append(self.mergeTwoLists(cur_list[i * 2], cur_list[i * 2 + 1]))
cur_list = cur_temp_list
return cur_list[0]