資訊專欄INFORMATION COLUMN
摘要：合并個(gè)已排序的鏈表合并個(gè)已排序的鏈表，新鏈表中的每個(gè)節(jié)點(diǎn)必須是來自輸入的原鏈表的節(jié)點(diǎn)即不能構(gòu)造新的節(jié)點(diǎn)，返回新鏈表的頭部。思路參照本人之前已發(fā)表的合并兩個(gè)已排序的鏈表，只需要將此算法應(yīng)用次即可得到新鏈表。
合并n個(gè)已排序的鏈表 Merge k Sorted Lists
合并n個(gè)已排序的鏈表，新鏈表中的每個(gè)節(jié)點(diǎn)必須是來自輸入的原鏈表的節(jié)點(diǎn)（即不能構(gòu)造新的節(jié)點(diǎ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
參照本人之前已發(fā)表的《合并兩個(gè)已排序的鏈表》，只需要將此算法應(yīng)用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，《合并兩個(gè)已排序鏈表》的代碼
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地址
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/40640.html
摘要：問題描述輸入兩個(gè)單調(diào)遞增的鏈表，輸出兩個(gè)鏈表合成后的鏈表，當(dāng)然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則。 1.問題描述 輸入兩個(gè)單調(diào)遞增的鏈表，輸出兩個(gè)鏈表合成后的鏈表，當(dāng)然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則。 2.思路 方法1:非遞歸方法 根據(jù)題目這個(gè)很類似排序中的外排過程,兩個(gè)數(shù)組分別排好序,然后再把他們整體進(jìn)行排序.所以這道題思想很簡單,就是用兩個(gè)變量分別遍歷兩個(gè)鏈表.比較遍歷到...
摘要：合并兩個(gè)已排序的鏈表合并兩個(gè)已排序的鏈表，新鏈表中的每個(gè)節(jié)點(diǎn)必須是來自輸入的兩個(gè)鏈表的節(jié)點(diǎn)即不能構(gòu)造新的節(jié)點(diǎn)，返回新鏈表的頭部。 合并兩個(gè)已排序的鏈表 Merge Two Sorted Lists 合并兩個(gè)已排序的鏈表，新鏈表中的每個(gè)節(jié)點(diǎn)必須是來自輸入的兩個(gè)鏈表的節(jié)點(diǎn)（即不能構(gòu)造新的節(jié)點(diǎn)），返回新鏈表的頭部。 Merge two sorted linked lists and ret...
摘要：分治算法遞歸每層操作分解將原問題分解成一系列的子問題。分治算法滿足的條件可分解原問題與分解成的小問題具有相同的模式無關(guān)聯(lián)原問題分解成的子問題可以獨(dú)立求解，子問題之間沒有相關(guān)性，這一點(diǎn)是分治算法跟動(dòng)態(tài)規(guī)劃的明顯區(qū)別。 Time：2019/4/10Title: Merge K Sorted ListsDifficulty: DifficultyAuthor: 小鹿 題目：Merge K...
摘要：既然說到地址空間了就順帶說一下上面環(huán)形鏈表這道題的另一種很的解法吧。介紹完常規(guī)操作鏈表的一些基本知識(shí)點(diǎn)后，現(xiàn)在回到快慢指針。 ??前幾天第一次在 Segmentfault 發(fā)文—JavaScript：十大排序的算法思路和代碼實(shí)現(xiàn)，發(fā)現(xiàn)大家似乎挺喜歡算法的，所以今天再分享一篇前兩個(gè)星期寫的 Leetcode 刷題總結(jié)，希望對(duì)大家能有所幫助。 ??本文首發(fā)于我的blog 前言 ??今天終于...
閱讀 3171·2021-11-19 09:40
閱讀 3663·2021-11-16 11:52
閱讀 2988·2021-11-11 16:55
閱讀 3186·2019-08-30 15:55
閱讀 1191·2019-08-30 13:08
閱讀 1664·2019-08-29 17:03
閱讀 3021·2019-08-29 16:19
閱讀 2587·2019-08-29 13:43
