leetcode 腾讯精选练习（50 题）23.合并k个排序链表

原题目

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input: [ 1->4->5, 1->3->4, 2->6 ] Output: 1->1->2->3->4->4->5->6

思路

用合并两条链表的方法合并k条链表，用归并合并的思想，每次合并两条链表最终合并成为一条链表

第一遍解法

# Runtime: 84 ms, faster than 69.50% of Python3 O(n) # Memory Usage: 16.3 MB, less than 75.11% of Python3 S(0) class Solution: def mergeKLists(self, lists): if lists == []: return None l = len(lists) while l != 1: for i in range(l // 2): lists[i] = self.mergeTwoLists(lists[i], lists[l-i-1]) if l % 2 == 0: l = l // 2 else: l = l // 2 + 1 return lists[0] def mergeTwoLists(self, l1, l2): if l1 == None or l2 == None: return l1 or l2 cur = l3 = ListNode(0) while l1 and l2: if l1.val <= l2.val: cur.next, l1 = l1, l1.next else: cur.next, l2 = l2, l2.next cur = cur.next cur.next = l1 or l2 return l3.next

网上好的解法

# 将每个节点的值都取出来排序后再赋值给节点 class Solution(object): def mergeKLists(self, lists): self.nodes = [] head = point = ListNode(0) for l in lists: while l: self.nodes.append(l.val) l = l.next for x in sorted(self.nodes): point.next = ListNode(x) point = point.next return head.next

自己可以改进的地方

最简代码

获得的思考