合并兩個(gè)排序的鏈表
考點(diǎn)：鏈表
題目描述
輸入兩個(gè)單調(diào)遞增的鏈表，輸出兩個(gè)鏈表合成后的鏈表收苏，當(dāng)然我們需要合成后的鏈表滿(mǎn)足單調(diào)不減規(guī)則亿卤。
代碼格式
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
}
}
image.png
注：鏈表1和鏈表2是兩個(gè)遞增排序的鏈表，合并這兩個(gè)鏈表得到升序鏈表為鏈表3.
解題一-遞歸
1.思路
首先分析合并兩個(gè)鏈表的過(guò)程鹿霸。我們的分析從合并兩個(gè)鏈表的頭結(jié)點(diǎn)開(kāi)始排吴。鏈表1的頭結(jié)點(diǎn)的值小于鏈表2的頭結(jié)點(diǎn)的值，因此鏈表1的頭結(jié)點(diǎn)將是合并后鏈表的頭結(jié)點(diǎn)懦鼠。如下圖所示钻哩。
image.png
- 鏈表1的頭結(jié)點(diǎn)的值小于鏈表2的頭結(jié)點(diǎn)的值，因此鏈表1的頭結(jié)點(diǎn)是合并后鏈表的頭結(jié)點(diǎn)肛冶。
- 在剩余的結(jié)點(diǎn)中街氢，鏈表2的頭結(jié)點(diǎn)的值小于鏈表1的頭結(jié)點(diǎn)的值，因此鏈表2的頭結(jié)點(diǎn)是剩余結(jié)點(diǎn)的頭結(jié)點(diǎn)睦袖，把這個(gè)結(jié)點(diǎn)和之前已經(jīng)合并好的鏈表的尾結(jié)點(diǎn)鏈接起來(lái)阳仔。
繼續(xù)合并兩個(gè)鏈表中剩余的結(jié)點(diǎn)（圖中虛線框所示）。在兩個(gè)鏈表中剩下的結(jié)點(diǎn)依然是排序的扣泊，因此合并這兩個(gè)鏈表的步驟和前面的步驟是一樣的近范。我們還是比較兩個(gè)頭結(jié)點(diǎn)的值。此時(shí)鏈表2的頭結(jié)點(diǎn)的值小于鏈表1的頭結(jié)點(diǎn)的值延蟹，因此鏈表2的頭結(jié)點(diǎn)的值將是合并剩余結(jié)點(diǎn)得到的鏈表的頭結(jié)點(diǎn)评矩。我們把這個(gè)結(jié)點(diǎn)和前面合并鏈表時(shí)得到的鏈表的尾結(jié)點(diǎn)（值為1的結(jié)點(diǎn)）鏈接起來(lái)，如圖所示阱飘。
2.代碼
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
ListNode head;
if (list1 == null) {
return list2;
}
if (list2 == null) {
return list1;
}
if(list1==null||list2==null){
return null;
}
if(list1.val<=list2.val){
head=list1;
head.next=Merge(list1.next,list2);
}else{
head=list2;
head.next=Merge(list1,list2.next);
}
return head;
}
}
解題二-非遞歸
2.代碼
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {//構(gòu)造方法
this.val = val;
}
}*/
public class Solution {
public ListNode Merge(ListNode list1,ListNode list2) {
//新建一個(gè)頭節(jié)點(diǎn)斥杜，用來(lái)存合并的鏈表虱颗。
ListNode head=new ListNode(-1);//為什么這樣子是新建一個(gè)頭結(jié)點(diǎn)？
//因?yàn)檫@樣子是利用了構(gòu)造方法創(chuàng)建一個(gè)鏈表
//其實(shí)也可以ListNode list = null;
head.next=null;
ListNode root=head;
if (list1 == null) {//還要判斷是不是空鏈表蔗喂，全部考慮玩所有的情況
return list2;
}
if (list2 == null) {
return list1;
}
while(list1!=null&&list2!=null){
if(list1.val<list2.val){
head.next=list1;
head=list1;
list1=list1.next;
}else{
head.next=list2;
head=list2;
list2=list2.next;
}
}
//把未結(jié)束的鏈表連接到合并后的鏈表尾部
if(list1!=null){
head.next=list1;
}
if(list2!=null){
head.next=list2;
}
return root.next; //返回頭結(jié)點(diǎn)
}
}
