Leetcode题库——23.合并k个排序链表

时间:2021-11-28 15:26:59

@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]