23. Merge k Sorted Lists

qingshanli1988 发布于2019-07-30 14:28 / 2263人阅读

摘要：题目合并排序链表并返回一个排序列表。分析和描述它的复杂性。直接对个链表合并，找到个链表头最小的，将值追加到放在新创建的链表中，并把头移到下一个节点，直到所有的链表头运行后发现超时尝试两两合并两个链表，知道最终合并成一个运行通过

题目

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
合并k排序链表并返回一个排序列表。分析和描述它的复杂性。

直接对k个链表合并，找到k个链表头最小的，将值追加到放在新创建的链表中，并把头移到下一个节点，直到所有的链表头none

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        head = None
        walk_list = [lists[i] for i in range(len(lists))]
        pre = None
        while len(filter(lambda x: x is not None, walk_list)):
            for i in range(len(walk_list)):
                if walk_list[i] is not None:
                    min_val = walk_list[i].val
                    min_index = i
                    break
            for i in range(len(walk_list)):
                if walk_list[i] and walk_list[i].val < min_val:
                    min_val = walk_list[i].val
                    min_index = i
            l = ListNode(min_val)
            walk_list[min_index] = walk_list[min_index].next
            if head is None:
                head = l
                pre = head
            else:
                pre.next = l
                pre = l
        return head

运行后发现超时

尝试两两合并两个链表，知道最终合并成一个

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """

        if not lists:
            return None
        i = 0
        j = len(lists) - 1
        r_list = lists
        while i < j:
            l = []
            while i < j:
                node = self.mergetwolists(r_list[i], r_list[j])
                l.append(node)
                i += 1
                j -= 1
            if i == j:
                l.append(r_list[i])
            r_list = l
            i = 0
            j = len(r_list) - 1
        return r_list[0]

    def mergetwolists(self, l1, l2):
        if l1 == None:
            return l2
        if l2 == None:
            return l1
        l1_head = l1
        l2_head = l2
        head = None
        pre = None
        while l1_head and l2_head:
            if l1_head.val < l2_head.val:
                l = ListNode(l1_head.val)
                l1_head = l1_head.next
            else:
                l = ListNode(l2_head.val)
                l2_head = l2_head.next

            if pre == None:
                pre = l
                head = l
            else:
                pre.next = l
                pre = l

            if l1_head is None:
                pre.next = l2_head
            if l2_head is None:
                pre.next = l1_head
        return head

运行通过

专线服务云服务器 Lists Sorted sorted-array sorted_set

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/40724.html

[LeetCode] 23. Merge k Sorted Lists

摘要：思路这题中的中，个还有其中个别的等于的情况，所以要判断一下再加入代码 Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. Heap Time Complexity: Update the heap costs O(nklogk) Space ...

Codeing_ls 2019-08-15 12:25 评论0 收藏0
LeetCode 之 JavaScript 解答第23题 —— 合并K个有序链表（Merge K S

摘要：分治算法递归每层操作分解将原问题分解成一系列的子问题。分治算法满足的条件可分解原问题与分解成的小问题具有相同的模式无关联原问题分解成的子问题可以独立求解，子问题之间没有相关性，这一点是分治算法跟动态规划的明显区别。 Time：2019/4/10Title: Merge K Sorted ListsDifficulty: DifficultyAuthor: 小鹿题目：Merge K...

zhou_you 2019-08-23 16:53 评论0 收藏0
355. Design Twitter , 用23. Merge k Sorted Lists和OO

摘要：的想法就是用每次得到最小的链表头的值，输出。每个都有一个关注人列表，用储存。用户可以发消息，关注别人，取消关注别人。可以系统得到关注人的消息合集，这个方法必须在这个层级。因为用户只知道自己的信息。 Merge k Sorted Lists /** * Definition for singly-linked list. * public class ListNode { * ...

1fe1se 2019-08-14 18:00 评论0 收藏0
[Leetcode] Merge Two Sorted Lists Merge K Sorted L

摘要：注意因为堆中是链表节点，我们在初始化堆时还要新建一个的类。代码初始化大小为的堆拿出堆顶元素将堆顶元素的下一个加入堆中 Merge Two Sorted Lists 最新更新请见：https://yanjia.me/zh/2019/01/... Merge two sorted linked lists and return it as a new list. The new list...

stefanieliang 2019-08-14 12:30 评论0 收藏0
[LintCode] Merge K Sorted Lists [DC/Heap]

摘要：分治做法中，函数依然是将链表结点两两进行比较，然后在函数中迭代两个二分后的结果。 Problem Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity. Example Given lists: [ 2->4->null, null, ...

happyhuangjinjin 2019-08-14 15:32 评论0 收藏0