資訊專欄INFORMATION COLUMN
摘要：合并兩個(gè)已排序的鏈表合并兩個(gè)已排序的鏈表，新鏈表中的每個(gè)節(jié)點(diǎn)必須是來(lái)自輸入的兩個(gè)鏈表的節(jié)點(diǎn)即不能構(gòu)造新的節(jié)點(diǎn)，返回新鏈表的頭部。
合并兩個(gè)已排序的鏈表 Merge Two Sorted Lists
合并兩個(gè)已排序的鏈表，新鏈表中的每個(gè)節(jié)點(diǎn)必須是來(lái)自輸入的兩個(gè)鏈表的節(jié)點(diǎn)（即不能構(gòu)造新的節(jié)點(diǎn)），返回新鏈表的頭部。
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
example 1
input: 1->2->4, 3->8 output: 1->2->3->4->8
head指向輸入兩個(gè)鏈表中頭節(jié)點(diǎn)較小值，作為新鏈表的頭部
tail指向新鏈表表尾，初始狀態(tài)head = tail
a掃描l1，b掃描l2，比較a和b節(jié)點(diǎn)內(nèi)值的大小，將較小的加入tail之后，a和b中較小的向后移動(dòng)一個(gè)節(jié)點(diǎn)，較大的不動(dòng)，tail向后移動(dòng)一個(gè)節(jié)點(diǎn)保證任意時(shí)候指向都是新鏈表尾部
l1和l2其中一個(gè)已經(jīng)遍歷完，若另一個(gè)還有元素，添加到tail之后
代碼# Definition for singly-linked list.
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
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://m.hztianpu.com/yun/38662.html
摘要：合并個(gè)已排序的鏈表合并個(gè)已排序的鏈表，新鏈表中的每個(gè)節(jié)點(diǎn)必須是來(lái)自輸入的原鏈表的節(jié)點(diǎn)即不能構(gòu)造新的節(jié)點(diǎn)，返回新鏈表的頭部。思路參照本人之前已發(fā)表的合并兩個(gè)已排序的鏈表，只需要將此算法應(yīng)用次即可得到新鏈表。 合并n個(gè)已排序的鏈表 Merge k Sorted Lists 合并n個(gè)已排序的鏈表，新鏈表中的每個(gè)節(jié)點(diǎn)必須是來(lái)自輸入的原鏈表的節(jié)點(diǎn)（即不能構(gòu)造新的節(jié)點(diǎn)），返回新鏈表的頭部。 Me...
摘要：?jiǎn)栴}描述輸入兩個(gè)單調(diào)遞增的鏈表，輸出兩個(gè)鏈表合成后的鏈表，當(dāng)然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則。 1.問(wèn)題描述 輸入兩個(gè)單調(diào)遞增的鏈表，輸出兩個(gè)鏈表合成后的鏈表，當(dāng)然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則。 2.思路 方法1:非遞歸方法 根據(jù)題目這個(gè)很類似排序中的外排過(guò)程,兩個(gè)數(shù)組分別排好序,然后再把他們整體進(jìn)行排序.所以這道題思想很簡(jiǎn)單,就是用兩個(gè)變量分別遍歷兩個(gè)鏈表.比較遍歷到...
摘要：需求實(shí)現(xiàn)函數(shù)進(jìn)行歸并排序。解法歸并排序的運(yùn)行方式是，遞歸的把一個(gè)大鏈表切分成兩個(gè)小鏈表。切分到最后就全是單節(jié)點(diǎn)鏈表了，而單節(jié)點(diǎn)鏈表可以被認(rèn)為是已經(jīng)排好序的。這時(shí)候再兩兩合并，最終會(huì)得到一個(gè)完整的已排序鏈表。用把排好序的兩個(gè)鏈表合并起來(lái)。 TL;DR 對(duì)鏈表進(jìn)行歸并排序，系列目錄見 前言和目錄 。 需求 實(shí)現(xiàn)函數(shù) mergeSort() 進(jìn)行歸并排序。注意這種排序法需要使用遞歸。在 fr...
摘要：題目描述輸入兩個(gè)單調(diào)遞增的鏈表，輸出兩個(gè)鏈表合成后的鏈表，當(dāng)然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則。 題目描述 輸入兩個(gè)單調(diào)遞增的鏈表，輸出兩個(gè)鏈表合成后的鏈表，當(dāng)然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則。 分析 首先考慮兩個(gè)鏈表的頭部哪個(gè)成為新鏈表的頭，顯然是值小的那個(gè)是新的頭；然后是合并時(shí)，兩個(gè)鏈表上分別有一個(gè)指針cur1和cur2，比較兩個(gè)指針指向的節(jié)點(diǎn)值大小，較小的鏈接到新鏈表的...
閱讀 1288·2021-11-25 09:43
閱讀 1654·2021-10-25 09:47
閱讀 2524·2019-08-30 13:46
閱讀 811·2019-08-29 13:45
閱讀 1336·2019-08-26 13:29
閱讀 3059·2019-08-23 15:30
閱讀 1169·2019-08-23 14:17
閱讀 1373·2019-08-23 13:43
