JZ16 --- 合并两个排序的列表

题目描述：

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

题解：

我们已知是两个递增的链表，需要把他合并成一个递增的链表。

（1）我们需要一个结果链表，表示最后合并后的链表。

（2）遍历两个链表，如果 cur1 < cur2，那么就说明 list1 的当前结点小于 list2 的当前结点，那么就需要把 cur1 排在前面，同时 cur1 也要后移。如果 cur1 >= cur2，那么就说明 list1 的当前结点大于 list2 的当前结点，那么就需要把 cur2 排在前面，同时 cur2 也要后移。

（3）我们需要注意的是，结果链表要继续合并链表，那么就需要一个 last 来标记当前结果链表的最后一个结点。last.next = cur ，就可以直接将我们比较得到的数据放置在链表末尾。

（4）重复步骤2，直至其中一个链表遍历结束。

cur1 > cur2

cur1 > cur2

遍历至 cur2 为空时，直接将 cur1 放置 res链表最末尾/。

最终得到合并之后的递增链表

public ListNode Merge(ListNode list1, ListNode lis
    if(list1 == null){
        return list2;
    }
    if(list2 == null){
        return list1;
    }
    ListNode cur1 = list1;
    ListNode cur2 = list2;
    ListNode res = null;  //结果链表
    ListNode last = null;  //结果链表的最后一个结点
    while(cur1 != null && cur2 != null){
        if(cur1.val < cur2.val){
            if(res == null){
                res = cur1;
            }
            else{
                last.next = cur1;
            }
            // 更新 last 和 cur1
            last = cur1;
            cur1 = cur1.next;
        }
        else{
            if(res == null){
                res = cur2;
            }else{
                last.next = cur2;
            }
            // 更新 last 和 cur2
            last = cur2;
            cur2 = cur2.next;
        }
        // 更新位置之后，必然会在某时某个链表遍历结束
        // 如果 cur1 遍历结束，则直接把剩下的 cur2 跟在后面
        if(cur1 != null){
            last.next = cur1;
        }else{
            // 如果 cur1 遍历结束，则直接把剩下的 cur2 跟在后面
            last.next = cur2;
        }
    }
    return res;
}