描述：

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。

数据范围： 0≤n≤1000，−1000≤节点值≤1000
要求：空间复杂度 O(1)，时间复杂度O(n)

如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}，转换过程如下图所示：

合并链表1.png

或输入{-1,2,4},{1,3,4}时，合并后的链表为{-1,1,2,3,4,4}，所以对应的输出为{-1,1,2,3,4,4}，转换过程如下图所示：

合并链表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}

合并链表，考虑到是有序列表，实现思路是：

1、增加一个带头节点的链表；
2、增加一个指针，在这个带头结点的链表上走动
3、最后返回头节点的next；

详细的编码：

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;
    }