将两个有序的链表合并为一个新链表，要求新的链表是通过拼接两个链表的节点来生成的，且合并后新链表依然有序。
ListNode:

public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}

示例1

输入

{1,3,5},{2,4,6}

返回值

{1,2,3,4,5,6}

1. 循环思路：

使用一个辅助节点dummy，以dummy作为表头构造一个新的链表。添加规则是：
依次比较list1和list2中每一个节点，把较小的那个添加在dummy之后

public class Solution {
    public ListNode Merge(ListNode l1, ListNode l2) {
    // basecase:
    if(l1 == null){
      return l2;
      }
    if(l2 == null){
      return l1;
      }

ListNode dummy = new ListNode(0);
ListNode cur = dummy;
// 循环比较：
    while(l1 != null && l2 != null){
      if(l1.val < l2.val){
                cur.next = l1;
                cur = cur.next;
                l1 = l1.next;
            }
      else {
              cur.next = l2;
              cur = cur.next;
              l2 = l2.next;
              }
            }

// return的是dummy的下一个节点，把dummy排除
return dummy.next;
}
}

2. 递归思路:

设置一个根节点mergeNode，然后递归返回较小的节点

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        ListNode mergeNode = null;
        if (l1.val < l2.val) {
            mergeNode = l1;
            mergeNode.next = mergeTwoLists(l1.next, l2);
        } else {
            mergeNode = l2;
            mergeNode.next = mergeTwoLists(l1, l2.next);
        }
        return mergeNode;
    }
}