合并两个排序的链表

给定两个递增的链表，合并成一个递增链表
如给1 3 5和2 4 6，合并后该为1 2 3 4 5 6

非递归方法

public ListNode merge(ListNode list1, ListNode list2) {
    if (list1 == null) {
        return list2;
    }
    if (list2 == null) {
        return list1;
    }
    if (list2 == null && list1 == null) {
        return null;
    }

    ListNode newStart, temp, temp2;
    newStart = list1;
    while (list1 != null && list2 != null) { 
        temp = null;
        temp2 = null;
        if (list1.val <= list2.val) {
            while (list1 != null && list1.val <= list2.val) {
                // 如果list2结点的值大于list1，将list1引用向后移
                // 直至list1的值大于list2或者list1为null
                // temp保存list1前面的结点，方便后面的插入操作
                temp = list1;
                list1 = list1.next;
            }
         }
        // temp2指向list2后面的结点
        temp2 = list2.next;
        // 这种情况表示list1指向第一个结点，也就是list1的第一个结点值小于list2第一个节点值
        if (temp == null) {
            list2.next = list1;
            // newStart为新的链表头结点
            newStart = list2;
        } else {
            // list2插入到list1中间
            list2.next = temp.next;
            temp.next = list2;
        }
          // 移动list2指向下一个结点
          list2 = temp2;
      }
      return newStart;
}

递归方法

public ListNode merge(ListNode list1, ListNode list2) {
     if (list1 == null) {
        return list2;
    }
    if (list2 == null) {
        return list1;
    }
    // 如果list1的值小于list2，将list1后面的结点和list2进行合并
    if (list1.val <= list2.val) {
        list1.next = merge(list1.next, list2);
        return list1;
    } else {
        // 否则将list2后面的结点跟list1进行合并
        list2.next = merge(list1, list2.next);
        return list2;
    }
}