描述：

輸入兩個(gè)遞增的鏈表，單個(gè)鏈表的長(zhǎng)度為n，合并這兩個(gè)鏈表并使新鏈表中的節(jié)點(diǎn)仍然是遞增排序的。

數(shù)據(jù)范圍： 0≤n≤1000，?1000≤節(jié)點(diǎn)值≤1000
要求：空間復(fù)雜度 O(1)，時(shí)間復(fù)雜度O(n)

如輸入{1,3,5},{2,4,6}時(shí)，合并后的鏈表為{1,2,3,4,5,6}，所以對(duì)應(yīng)的輸出為{1,2,3,4,5,6}，轉(zhuǎn)換過程如下圖所示：

合并鏈表1.png

或輸入{-1,2,4},{1,3,4}時(shí)，合并后的鏈表為{-1,1,2,3,4,4}，所以對(duì)應(yīng)的輸出為{-1,1,2,3,4,4}，轉(zhuǎn)換過程如下圖所示：

合并鏈表2.png

示例1

輸入：{1,3,5},{2,4,6}
返回值：{1,2,3,4,5,6}

示例2

輸入：{},{}
返回值：{}

示例3

輸入：{-1,2,4},{1,3,4}
返回值：{-1,1,2,3,4,4}

合并鏈表，考慮到是有序列表，實(shí)現(xiàn)思路是：

1、增加一個(gè)帶頭節(jié)點(diǎn)的鏈表；
2、增加一個(gè)指針，在這個(gè)帶頭結(jié)點(diǎn)的鏈表上走動(dòng)
3、最后返回頭節(jié)點(diǎn)的next；

詳細(xì)的編碼：

public ListNode Merge(ListNode list1, ListNode list2) {
        ListNode head = new ListNode(-1);
        ListNode prev = head;
        while (list1 != null && list2 != null) {
            if (list1.val > list2.val) {//list2的值偏小
                prev.next = list2;//把list2的值加入到新的鏈表中
                list2 = list2.next;
            } else {
                prev.next = list1;//把list1的值加入到新的鏈表中
                list1 = list1.next;
            }
            prev = prev.next;
        }
        if (list1 != null) {
            prev.next = list1;//把list1賦值給prev
        }
        if (list2 != null) {
            prev.next = list2;//把list2賦值給prev
        }
        return head.next;
    }