合并兩個已排序的鏈表

ormsf 發布于2019-07-25 12:04 / 3311人閱讀

摘要：合并兩個已排序的鏈表合并兩個已排序的鏈表，新鏈表中的每個節點必須是來自輸入的兩個鏈表的節點即不能構造新的節點，返回新鏈表的頭部。

合并兩個已排序的鏈表 Merge Two Sorted Lists

合并兩個已排序的鏈表，新鏈表中的每個節點必須是來自輸入的兩個鏈表的節點（即不能構造新的節點），返回新鏈表的頭部。

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指向輸入兩個鏈表中頭節點較小值，作為新鏈表的頭部

tail指向新鏈表表尾，初始狀態head = tail

a掃描l1，b掃描l2，比較a和b節點內值的大小，將較小的加入tail之后，a和b中較小的向后移動一個節點，較大的不動，tail向后移動一個節點保證任意時候指向都是新鏈表尾部

l1和l2其中一個已經遍歷完，若另一個還有元素，添加到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地址

GPU云服務器云服務器鏈表排序合并鏈表的c語言鏈表排序算法合并排序

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

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/38662.html

合并n個已排序的鏈表

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

HtmlCssJs 2019-07-30 14:19 評論0 收藏0
劍指offer:合并兩個排序的鏈表（Java）

摘要：問題描述輸入兩個單調遞增的鏈表，輸出兩個鏈表合成后的鏈表，當然我們需要合成后的鏈表滿足單調不減規則。 1.問題描述輸入兩個單調遞增的鏈表，輸出兩個鏈表合成后的鏈表，當然我們需要合成后的鏈表滿足單調不減規則。 2.思路方法1:非遞歸方法根據題目這個很類似排序中的外排過程,兩個數組分別排好序,然后再把他們整體進行排序.所以這道題思想很簡單,就是用兩個變量分別遍歷兩個鏈表.比較遍歷到...

darkbaby123 2019-08-16 18:39 評論0 收藏0
用 JavaScript 實現鏈表操作 - 15 Merge Sort

摘要：需求實現函數進行歸并排序。解法歸并排序的運行方式是，遞歸的把一個大鏈表切分成兩個小鏈表。切分到最后就全是單節點鏈表了，而單節點鏈表可以被認為是已經排好序的。這時候再兩兩合并，最終會得到一個完整的已排序鏈表。用把排好序的兩個鏈表合并起來。 TL;DR 對鏈表進行歸并排序，系列目錄見前言和目錄。需求實現函數 mergeSort() 進行歸并排序。注意這種排序法需要使用遞歸。在 fr...

X_AirDu 2019-08-20 14:23 評論0 收藏0
【刷算法】合并兩個排序的單鏈表

摘要：題目描述輸入兩個單調遞增的鏈表，輸出兩個鏈表合成后的鏈表，當然我們需要合成后的鏈表滿足單調不減規則。題目描述輸入兩個單調遞增的鏈表，輸出兩個鏈表合成后的鏈表，當然我們需要合成后的鏈表滿足單調不減規則。分析首先考慮兩個鏈表的頭部哪個成為新鏈表的頭，顯然是值小的那個是新的頭；然后是合并時，兩個鏈表上分別有一個指針cur1和cur2，比較兩個指針指向的節點值大小，較小的鏈接到新鏈表的...

2501207950 2019-08-22 18:26 評論0 收藏0