LeetCode 21：合并兩個有序鏈表 Merge Two Sorted Lists

LeviDing 發布于2019-07-31 11:31 / 3354人閱讀

摘要：將兩個有序鏈表合并為一個新的有序鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節點組成的。無非是依次將兩個鏈表每個節點的值對比，取出值較小的節點，添加到新鏈表末尾。將剩余鏈表傳回遞歸函數。

將兩個有序鏈表合并為一個新的有序鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節點組成的。

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.

示例：

輸入：1->2->4, 1->3->4
輸出：1->1->2->3->4->4

解題思路：

迭代和遞歸都能解題。無非是依次將兩個鏈表每個節點的值對比，取出值較小的節點，添加到新鏈表末尾。然后繼續比較兩個鏈表，直到其中一個鏈表遍歷完成，此時另一個鏈表剩余所有節點直接添加到新鏈表之后即可。其邏輯為：

原鏈表：1->2->4->null，1->3->4->5->6->null
依次對比節點值，取出各自頭節點：1 = 1
值相同取出一個節點 1，組成新鏈表：1
此時原鏈表：2->4->null，1->3->4->5->6->null對比頭節點值：2 > 1
取出 1 節點，添加到新鏈表末尾：1->1
此時原鏈表：2->4->null，3->4->5->6->null
對比頭節點值：2 < 3
取出 2 節點，添加到新鏈表末尾：1->1->2
此時原鏈表：4->null，3->4->5->6->null
.......依次類推，直到其中一個原鏈表為空時：
原鏈表：null，4->5->6->null
新鏈表：1->1->2->3->4
這時其中一個原鏈表已經為空，則直接將另一個原鏈表添加到新鏈表末尾即可：
1->1->2->3->4->4->5->6->null

迭代法：

迭代法需要注意：先判斷原鏈表是否為空；對比原鏈表第一個節點值的大小，選擇較小一個作為新鏈表的頭節點。之后才能按上述邏輯執行。

如果添加一個虛擬節點作為頭節點，則無需上述條件，但應當返回虛擬節點的下一個節點。

Java：

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(-1);//新建虛擬頭節點
        ListNode cur = head;//當前節點指向虛擬頭節點
        while (l1 != null && l2 != null) {//循環條件為鏈表都不為空
            if (l1.val < l2.val) {//比較頭節點的值的大小
                cur.next = l1;//當前節點連接到節點值較小的一個
                l1 = l1.next;//刷新原鏈表頭節點
                cur = cur.next;//刷新當前節點
            } else {
                cur.next = l2;
                l2 = l2.next;
                cur = cur.next;
            }
        }
        if (l1 == null) cur.next = l2;//選擇另外一個不為空的原鏈表，連接到新鏈表末尾
        else cur.next = l1;
        return head.next;//返回虛擬頭節點的下一個節點，即真實頭節點
    }
}

Python3：

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        head = ListNode(-1)
        cur = head;
        while l1 and l2:
            if l1.val <= l2.val:
                cur.next = l1
                cur = cur.next
                l1 = l1.next
            else:
                cur.next = l2
                cur = cur.next
                l2 = l2.next
        if l1:
            cur.next = l1
        else:
            cur.next = l2
        return head.next

遞歸法：

遞歸基線條件為：原鏈表其中之一遇到空節點。返回值為：另一個鏈表剩余部分的頭節點。

遞歸判斷頭節點的值的大小，取小的節點添加到新鏈表之后。將剩余鏈表傳回遞歸函數。

Java：

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;//基線條件
        if (l2 == null) return l1;//基線條件
        ListNode head;
        if (l1.val <= l2.val) {//選擇節點值較小的節點
            head = l1;//刷新頭節點
            head.next = mergeTwoLists(l1.next, l2);//剩余鏈表作為參數傳入遞歸函數
        } else {
            head = l2;
            head.next = mergeTwoLists(l1, l2.next);
        }
        return head;
    }
}

Python3：

class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        if not l1: return l2
        if not l2: return l1
        if l1.val <= l2.val:
            head = l1
            head.next = self.mergeTwoLists(l1.next, l2)
        else:
            head = l2
            head.next = self.mergeTwoLists(l1, l2.next)
        return head

歡迎關注微.信公.眾號：愛寫Bug

云服務器 GPU云服務器合并鏈表的c語言合并兩個單鏈表 linux 兩個硬盤合并 js 兩個數據合并

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

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

LeetCode 之 JavaScript 解答第21題 —— 合并兩個有序鏈表（Merge Two

摘要：什么意思呢比如上方合并鏈表的代碼，分別明確函數的參數和返回值是什么參數是兩個合并的鏈表結點頭結點。返回值是合并后的鏈表。 Time：2019/4/9Title: Merge Two Sorted ListsDifficulty: EasyAuthor: 小鹿題目：Merge Two Sorted Lists Merge two sorted linked lists and re...

wdzgege 2019-08-23 16:51 評論0 收藏0
leetcode21 Merge Two Sorted Lists 將兩個有序鏈表組合成一個新的有

摘要：題目要求翻譯過來就是將兩個有序的鏈表組合成一個新的有序的鏈表思路一循環在當前兩個鏈表的節點都是非空的情況下比較大小，較小的添入結果鏈表中并且獲得較小節點的下一個節點。題目要求 Merge two sorted linked lists and return it as a new list. The new list should be made by splicing togeth...

BothEyes1993 2019-08-14 18:05 評論0 收藏0
Leetcode 21 Merge Two Sorted Lists

摘要：題目詳情題目要求我們將兩個有序鏈表合成一個有序的鏈表。輸入輸出想法首先要判斷其中一個鏈表為空的狀態，這種情況直接返回另一個鏈表即可。每次遞歸都會獲得當前兩個鏈表指針位置的值較小的節點，從而組成一個新的鏈表。題目詳情 Merge two sorted linked lists and return it as a new list. The new list should be mad...

xbynet 2019-08-14 18:01 評論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 攻略 - 2019 年 7 月上半月匯總（55 題攻略）

摘要：微信公眾號記錄截圖記錄截圖目前關于這塊算法與數據結構的安排前。已攻略返回目錄目前已攻略篇文章。會根據題解以及留言內容，進行補充，并添加上提供題解的小伙伴的昵稱和地址。本許可協議授權之外的使用權限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目錄不...

warmcheng 2019-08-26 10:09 評論0 收藏0