資訊專欄INFORMATION COLUMN
摘要：將兩個(gè)有序鏈表合并為一個(gè)新的有序鏈表并返回。新鏈表是通過拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的。無非是依次將兩個(gè)鏈表每個(gè)節(jié)點(diǎn)的值對(duì)比，取出值較小的節(jié)點(diǎn)，添加到新鏈表末尾。將剩余鏈表傳回遞歸函數(shù)。
將兩個(gè)有序鏈表合并為一個(gè)新的有序鏈表并返回。新鏈表是通過拼接給定的兩個(gè)鏈表的所有節(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.
示例：
輸入：1->2->4, 1->3->4 輸出：1->1->2->3->4->4解題思路：
迭代和遞歸都能解題。無非是依次將兩個(gè)鏈表每個(gè)節(jié)點(diǎn)的值對(duì)比，取出值較小的節(jié)點(diǎn)，添加到新鏈表末尾。然后繼續(xù)比較兩個(gè)鏈表，直到其中一個(gè)鏈表遍歷完成，此時(shí)另一個(gè)鏈表剩余所有節(jié)點(diǎn)直接添加到新鏈表之后即可。其邏輯為：
原鏈表：1->2->4->null，1->3->4->5->6->null迭代法：
依次對(duì)比節(jié)點(diǎn)值，取出各自頭節(jié)點(diǎn)：1 = 1
值相同取出一個(gè)節(jié)點(diǎn) 1，組成新鏈表：1
此時(shí)原鏈表：2->4->null，1->3->4->5->6->null對(duì)比頭節(jié)點(diǎn)值：2 > 1
取出 1 節(jié)點(diǎn)，添加到新鏈表末尾：1->1
此時(shí)原鏈表：2->4->null，3->4->5->6->null對(duì)比頭節(jié)點(diǎn)值：2 < 3
取出 2 節(jié)點(diǎn)，添加到新鏈表末尾：1->1->2
此時(shí)原鏈表：4->null，3->4->5->6->null.......依次類推，直到其中一個(gè)原鏈表為空時(shí)：
原鏈表：null，4->5->6->null
新鏈表：1->1->2->3->4
這時(shí)其中一個(gè)原鏈表已經(jīng)為空，則直接將另一個(gè)原鏈表添加到新鏈表末尾即可：
1->1->2->3->4->4->5->6->null
迭代法需要注意：先判斷原鏈表是否為空；對(duì)比原鏈表第一個(gè)節(jié)點(diǎn)值的大小，選擇較小一個(gè)作為新鏈表的頭節(jié)點(diǎn)。之后才能按上述邏輯執(zhí)行。
如果添加一個(gè)虛擬節(jié)點(diǎn)作為頭節(jié)點(diǎn)，則無需上述條件，但應(yīng)當(dāng)返回虛擬節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)。
Java：
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode head = new ListNode(-1);//新建虛擬頭節(jié)點(diǎn)
ListNode cur = head;//當(dāng)前節(jié)點(diǎn)指向虛擬頭節(jié)點(diǎn)
while (l1 != null && l2 != null) {//循環(huán)條件為鏈表都不為空
if (l1.val < l2.val) {//比較頭節(jié)點(diǎn)的值的大小
cur.next = l1;//當(dāng)前節(jié)點(diǎn)連接到節(jié)點(diǎn)值較小的一個(gè)
l1 = l1.next;//刷新原鏈表頭節(jié)點(diǎn)
cur = cur.next;//刷新當(dāng)前節(jié)點(diǎn)
} else {
cur.next = l2;
l2 = l2.next;
cur = cur.next;
}
}
if (l1 == null) cur.next = l2;//選擇另外一個(gè)不為空的原鏈表，連接到新鏈表末尾
else cur.next = l1;
return head.next;//返回虛擬頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，即真實(shí)頭節(jié)點(diǎn)
}
}
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
遞歸法：
遞歸基線條件為：原鏈表其中之一遇到空節(jié)點(diǎn)。返回值為：另一個(gè)鏈表剩余部分的頭節(jié)點(diǎn)。
遞歸判斷頭節(jié)點(diǎn)的值的大小，取小的節(jié)點(diǎn)添加到新鏈表之后。將剩余鏈表傳回遞歸函數(shù)。
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) {//選擇節(jié)點(diǎn)值較小的節(jié)點(diǎn)
head = l1;//刷新頭節(jié)點(diǎn)
head.next = mergeTwoLists(l1.next, l2);//剩余鏈表作為參數(shù)傳入遞歸函數(shù)
} 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
歡迎關(guān)注 微.信公.眾號(hào)：愛寫B(tài)ug
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/45248.html
摘要：什么意思呢比如上方合并鏈表的代碼，分別明確函數(shù)的參數(shù)和返回值是什么參數(shù)是兩個(gè)合并的鏈表結(jié)點(diǎn)頭結(jié)點(diǎn)。返回值是合并后的鏈表。 Time：2019/4/9Title: Merge Two Sorted ListsDifficulty: EasyAuthor: 小鹿 題目：Merge Two Sorted Lists Merge two sorted linked lists and re...
摘要：題目要求翻譯過來就是將兩個(gè)有序的鏈表組合成一個(gè)新的有序的鏈表思路一循環(huán)在當(dāng)前兩個(gè)鏈表的節(jié)點(diǎn)都是非空的情況下比較大小，較小的添入結(jié)果鏈表中并且獲得較小節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)。 題目要求 Merge two sorted linked lists and return it as a new list. The new list should be made by splicing togeth...
摘要：題目詳情題目要求我們將兩個(gè)有序鏈表合成一個(gè)有序的鏈表。輸入輸出想法首先要判斷其中一個(gè)鏈表為空的狀態(tài)，這種情況直接返回另一個(gè)鏈表即可。每次遞歸都會(huì)獲得當(dāng)前兩個(gè)鏈表指針位置的值較小的節(jié)點(diǎn)，從而組成一個(gè)新的鏈表。 題目詳情 Merge two sorted linked lists and return it as a new list. The new list should be mad...
摘要：分治算法遞歸每層操作分解將原問題分解成一系列的子問題。分治算法滿足的條件可分解原問題與分解成的小問題具有相同的模式無關(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...
摘要：微信公眾號(hào)記錄截圖記錄截圖目前關(guān)于這塊算法與數(shù)據(jù)結(jié)構(gòu)的安排前。已攻略返回目錄目前已攻略篇文章。會(huì)根據(jù)題解以及留言內(nèi)容，進(jìn)行補(bǔ)充，并添加上提供題解的小伙伴的昵稱和地址。本許可協(xié)議授權(quán)之外的使用權(quán)限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一 目錄 不...
閱讀 4391·2021-11-19 09:59
閱讀 3319·2021-10-12 10:12
閱讀 2631·2021-09-22 15:25
閱讀 3321·2019-08-30 15:55
閱讀 1183·2019-08-29 11:27
閱讀 1463·2019-08-28 18:06
閱讀 2736·2019-08-26 13:41
閱讀 2554·2019-08-26 13:41
