合并n個已排序的鏈表

HtmlCssJs 發布于2019-07-30 14:19 / 1649人閱讀

摘要：合并個已排序的鏈表合并個已排序的鏈表，新鏈表中的每個節點必須是來自輸入的原鏈表的節點即不能構造新的節點，返回新鏈表的頭部。思路參照本人之前已發表的合并兩個已排序的鏈表，只需要將此算法應用次即可得到新鏈表。

合并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語言鏈表排序算法合并排序

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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