题解 | #合并两个排序的链表#

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

输入： {1,3,5},{2,4,6}

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

首先思路很简单，一个while循环，里面进行比较，让新链表指针指向小的那个节点，然后移动指针，直到全部补全链表。
先附上代码，没有使用递归方法。

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode result = new ListNode(0);
        ListNode list = result;
        while(list1!=null&&list2!=null){
            if(list1.val > list2.val){
                list.next = list2;
                list2 = list2.next;
            }
            else if(list1.val == list2.val){
                list.next = list1;
                list1 = list1.next;
                list.next.next = list2;
                list2 = list2.next;
                list = list.next;
            }
            else if(list1.val < list2.val ){
                list.next = list1;
                list1 = list1.next;
            }
            else{
                return null;
            }
            list = list.next;
        }
        if (list1 == null && list2 != null) list.next = list2;
        if (list2 == null && list1 != null) list.next = list1;
        return result.next;
    }
}

简单说一下遇到的几个问题：

1. 直接将节点值赋给新链表
这样不行的原因是新的链表没有成型，导致在对list.next.value()赋值时发现根本就没有这个节点，会报空指针异常。所以我们应直接将新链表连在原来的链表上，使用原来链表的节点。
2.注意将一个链表扫描完后，另一个还没结束，这时不能再在while循环里想办法兼容，直接在while循环外一个if解决问题。因为while循环的条件是两个链表都不为空！！