21. Merge Two Sorted Lists

題目：
給定兩個 已排序的單向鏈表 list1 和 list2，將它們合併成一個排序好的鏈表並返回新鏈表的頭節點

範例：

• Example 1:
  Input: list1 = [1,2,4], list2 = [1,3,4]
  Output: [1,1,2,3,4,4]

• Example 2:
  Input: list1 = [], list2 = []
  Output: []

• Example 3:
  Input: list1 = [], list2 = [0]
  Output: [0]

想法：
先判斷list是否為空
是：1. 1個list：換成MAX_VALUE比較
2. 皆為空：離開
否：繼續執行

程式碼：

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(0); //先生成最開始用來接到第一個node的dummy node
        ListNode current = dummy;         //current node用來做遍歷使用
        while( list1 != null || list2 != null){
            int v1 = (list1 == null? Integer.MAX_VALUE: list1.val);
            int v2 = (list2 == null? Integer.MAX_VALUE: list2.val);

        if (v1 < v2){ //比較兩點的值
            current.next = list1;  //比較小的節點接到current的next上面
            list1 = list1.next;    //對應的list指標往下走
        } else {
            current.next = list2;  
            list2 = list2.next;
        }
        current = current.next;   //current指標往下走
        current.next = null;      //current的下一個節點重設為null（如不重設，會是接入list1/list2的next）
        } 
    return dummy.next;
    }
}

while( list1 != null || list2 != null)
——＞當list非空則繼續重複直到兩者皆為空
且
int v1 = (list1 == null? Integer.MAX_VALUE: list1.val);
int v2 = (list2 == null? Integer.MAX_VALUE: list2.val);
——＞表示每次迴圈皆需重新判斷，運用Integer.MAX_VALUE使變數需額外計算——＞較浪費時間效率低

實際操作：

list1 = 1 -> 2 -> 4
list2 = 1 -> 3 -> 4

STEP1:
v1=1, v2=1 ——＞放入v2的1
list2 -> 3
dummy.next = 1

STEP2:
v1=1, v2=3 ——＞放入v1的1
list1 -> 2
dummy.next = 1->1

STEP3:
v1=2, v2=3 ——＞放入v1的2
list1 -> 4
dummy.next = 1->1->2

STEP4:
v1=4, v2=3 ——＞放入v2的3
list2 -> 4
dummy.next = 1->1->2->3

STEP5:
v1=4, v2=4 ——＞放入v2的4
list2 -> null
dummy.next = 1->1->2->3->4

STEP6:
v1=4, v2=INF ——＞放入v1的4
list1 -> null
dummy.next = 1->1->2->3->4->4

結束：list1=null && list2=null
return dummy.next = 1->1->2->3->4->4