合并n个已排序的链表

HtmlCssJs 发布于2019-07-30 14:19 / 1630人阅读

摘要：合并个已排序的链表合并个已排序的链表，新链表中的每个节点必须是来自输入的原链表的节点即不能构造新的节点，返回新链表的头部。思路参照本人之前已发表的合并两个已排序的链表，只需要将此算法应用次即可得到新链表。

合并n个已排序的链表 Merge k Sorted Lists

合并n个已排序的链表，新链表中的每个节点必须是来自输入的原链表的节点（即不能构造新的节点），返回新链表的头部。

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

example 1

input:
[
  3->5->8,
  2->11>12,
  4->8,
]
output:
2->3->4->5->8->8->11->12

思路

参照本人之前已发表的《合并两个已排序的链表》，只需要将此算法应用n-1次即可得到新链表。

代码

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

    def __cmp__(self, other):
        return self.val <= other




class Solution(object):

    def mergeKLists_new(self, links):
        """
        :type links: List[ListNode]
        :rtype: ListNode
        """
        head = None
        for i in links:
            head = self.mergeTwoLists(head, i)
        return head


    # 为了方便阅读，给出之前的代码
    # from mergeTwoLists，《合并两个已排序链表》的代码
    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if None in (l1, l2):
            return l1 or l2
        head = tail = l1 if l1.val <= l2.val else l2
        a = l1 if l1.val > l2.val else l1.next
        b = l2 if l1.val <= l2.val else l2.next
        while a and b:
            if a.val <= b.val:
                tail.next = a
                tail, a = tail.next, a.next
            else:
                tail.next = b
                tail, b = tail.next, b.next
        tail.next = a or b
        return head

本题以及其它leetcode题目代码github地址: github地址

云服务器 GPU云服务器链表排序合并链表的c语言链表排序算法合并排序

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

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

剑指offer:合并两个排序的链表（Java）

摘要：问题描述输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。 1.问题描述输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。 2.思路方法1:非递归方法根据题目这个很类似排序中的外排过程,两个数组分别排好序,然后再把他们整体进行排序.所以这道题思想很简单,就是用两个变量分别遍历两个链表.比较遍历到...

darkbaby123 2019-08-16 18:39 评论0 收藏0
合并两个已排序的链表

摘要：合并两个已排序的链表合并两个已排序的链表，新链表中的每个节点必须是来自输入的两个链表的节点即不能构造新的节点，返回新链表的头部。合并两个已排序的链表 Merge Two Sorted Lists 合并两个已排序的链表，新链表中的每个节点必须是来自输入的两个链表的节点（即不能构造新的节点），返回新链表的头部。 Merge two sorted linked lists and ret...

ormsf 2019-07-25 12:04 评论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
Leetcode：刷完31道链表题的一点总结

摘要：既然说到地址空间了就顺带说一下上面环形链表这道题的另一种很的解法吧。介绍完常规操作链表的一些基本知识点后，现在回到快慢指针。前几天第一次在 Segmentfault 发文—JavaScript：十大排序的算法思路和代码实现，发现大家似乎挺喜欢算法的，所以今天再分享一篇前两个星期写的 Leetcode 刷题总结，希望对大家能有所帮助。本文首发于我的blog 前言今天终于...

DevTalking 2019-08-23 17:50 评论0 收藏0