LeetCode演算法題-Merge Two Sorted List
摘要：
這是悅樂書的第 148 次更新，第 150 篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第7題（順位題號是21）。合併兩個已排序的連結串列並將其作為新連結串列返回。 新連結串列應該通過拼接前兩個連結串列的節點來完成。例如：
...
這是悅樂書的第 148 次更新，第 150 篇原創
01 看題和準備
今天介紹的是LeetCode演算法題中Easy級別的第7題（順位題號是21）。合併兩個已排序的連結串列並將其作為新連結串列返回。 新連結串列應該通過拼接前兩個連結串列的節點來完成。例如：
連結串列L1包含三個節點，為1,2,4
連結串列L2包含三個節點，為1,3,4
將L1和L2合併後的新連結串列包含6個節點，為1,1,2,3,4,4
本次解題使用的開發工具是eclipse，jdk使用的版本是1.8，環境是win7 64位系統，使用Java語言編寫和測試。
02 此題中的連結串列是什麼？
先來看段程式碼，下面是定義的ListNode類，有兩個屬性，一個是儲存整數值的val，一個是ListNode類本身的next，儲存下一個ListNode的地址值（指標）。形象的解釋就是，連結串列可以是拉鍊的齒輪，互相咬合；也可以是電影《盜夢空間》中的夢中夢；就像大盒子裡面可以繼續放盒子一樣。
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
為了更好的理解連結串列是怎麼儲存值的，且看下面的程式碼。l1的next屬性引用了l2，l2的next屬性引用了l3。
public class Easy_21_MergeTwoSortedList {
public static void main(String[] args) {
Easy_21_MergeTwoSortedList instance = new Easy_21_MergeTwoSortedList();
ListNode l1 = new ListNode(1);
ListNode l2 =new ListNode(2);
ListNode l3 =new ListNode(4);
l1.next = l2;
l2.next = l3;
System.out.println(instance.listNodeToString(l1));
ListNode l4 = new ListNode(1);
ListNode l5 =new ListNode(3);
ListNode l6 =new ListNode(4);
l4.next = l5;
l5.next = l6;
System.out.println(instance.listNodeToString(l4));
}
public String listNodeToString(ListNode L){
List<Integer> list = new ArrayList<Integer>();
while(L != null){
list.add(L.val);
L = L.next;
}
return list.toString();
}
}
03 第一種解法
因為給的連結串列都是已經排過序的（由小到大），只需要依次比較兩個連結串列的元素val值即可，並且存入一個新的連結串列裡面。如果某一個連結串列先迴圈完，新連結串列剩下的元素就是另外一個連結串列剩下的元素。
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
cur.next = l1;
l1 = l1.next;
} else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
04 第二種解法
像第二種方法迴圈判斷再取值的情況，很容易聯想到遞迴，即自己呼叫自己，同時給予退出條件即可。使用遞迴的好處就是程式碼量少。
public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
if (l1.val < l2.val) {
l1.next = mergeTwoLists2(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists2(l1, l2.next);
return l2;
}
}
05 小結
此題雖然不難，但是需要先將題目意思讀懂，並且知道連結串列是怎麼存資料的，這樣才能更好解題。為了更好理解，下面貼上全部程式碼。
package leetcode;
import java.util.ArrayList;
import java.util.List;
/**
* 合併兩個已排序的連結列表並將其作為新列表返回。 新列表應該通過拼接前兩個列表的節點來完成。
* 例：
* 輸入：1-> 2-> 4, 1-> 3-> 4
* 輸出：1-> 1-> 2-> 3-> 4-> 4
* @author 小川94
* @date 2018-10-21
*/
public class Easy_21_MergeTwoSortedList {
public static void main(String[] args) {
Easy_21_MergeTwoSortedList instance = new Easy_21_MergeTwoSortedList();
ListNode l1 = new ListNode(1);
ListNode l2 =new ListNode(2);
ListNode l3 =new ListNode(4);
l1.next = l2;
l2.next = l3;
System.out.println(instance.listNodeToString(l1));
ListNode l4 = new ListNode(1);
ListNode l5 =new ListNode(3);
ListNode l6 =new ListNode(4);
l4.next = l5;
l5.next = l6;
System.out.println(instance.listNodeToString(l4));
ListNode result = instance.mergeTwoLists2(l1, l4);
System.out.println(instance.listNodeToString(result));
}
public String listNodeToString(ListNode L){
List<Integer> list = new ArrayList<Integer>();
while(L != null){
list.add(L.val);
L = L.next;
}
return list.toString();
}
/**
* 順位迴圈判斷
* @param l1
* @param l2
* @return
*/
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
cur.next = l1;
l1 = l1.next;
} else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = (l1 != null) ? l1 : l2;
return dummy.next;
}
/**
* 利用遞迴
* @param l1
* @param l2
* @return
*/
public ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
if (l1.val < l2.val) {
l1.next = mergeTwoLists2(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists2(l1, l2.next);
return l2;
}
}
}
class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
此題解法遠不止上面這兩種，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！