LeetCode-合併兩個有序連結串列

語言: CN / TW / HK

theme: channing-cyan

這是我參與11月更文挑戰的第5天,活動詳情檢視:2021最後一次更文挑戰

題目

將兩個升序連結串列合併為一個新的 升序 連結串列並返回。新連結串列是通過拼接給定的兩個連結串列的所有節點組成的。 

image.png

  • 示例 1:

輸入:l1 = [1,2,4], l2 = [1,3,4] 輸出:[1,1,2,3,4,4] - 示例 2:

輸入:l1 = [], l2 = [] 輸出:[] - 示例 3:

輸入:l1 = [], l2 = [0] 輸出:[0]  

提示:

兩個連結串列的節點數目範圍是 [0, 50] -100 <= Node.val <= 100 l1 和 l2 均按 非遞減順序 排列

解題:

先了解什麼是升序連結串列:

連結串列(Linked list)是一種常見的基礎資料結構,是一種線性表

升序連結串列中,資料是按照關鍵值有序排列的,並且是從小到大排序

什麼是遞迴演算法?

遞迴演算法(recursion algorithm)在電腦科學中是指一種通過重複將問題分解為同類的子問題而解決問題的方法。

閱讀遞迴函式最容易的方法不是糾纏於它的執行過程,而是相信遞迴函式會順利完成它的任務。而我們寫遞迴函式要考慮的是每個步驟正確無誤,限制條件設定正確,並且每次呼叫之後更接近限制條件,遞迴函式總是能正確的完成任務。

考慮邊界值:

題目要求新連結串列是通過拼接給定的兩個連結串列的所有節點組成的,那麼有以下的情況 - 其中一個為空連結串列,那麼新連結串列則等於另一個連結串列 - 兩個都是空連結串列,這樣拼接組成的新連結串列也是空連結串列 - 兩個連結串列都不為空: 從兩個連結串列節點的值進行判斷,把節點值小的連結串列指向的下一節點傳下去,而另外的連結串列則把當前節點傳下去繼續進行節點值的比較,知道遞迴呼叫中某一個連結串列引數為空,則退出遞迴呼叫,向上逐層返回連結串列結果

實現

java class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { // 其中一個為空連結串列,那麼新連結串列則等於另一個連結串列 if(list1 == null){ return list2; } else if(list2 == null){ return list1; } else if(list1.val < list2.val){ // 遞迴呼叫 list1.next = mergeTwoLists(list1.next, list2); return list1; } else { // 遞迴呼叫 list2.next = mergeTwoLists(list1, list2.next); return list2; } } }