將兩個(gè)有序的鏈表合并為一個(gè)新鏈表，要求新的鏈表是通過(guò)拼接兩個(gè)鏈表的節(jié)點(diǎn)來(lái)生成的，且合并后新鏈表依然有序。
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. 循環(huán)思路：

使用一個(gè)輔助節(jié)點(diǎn)dummy，以dummy作為表頭構(gòu)造一個(gè)新的鏈表。添加規(guī)則是：
依次比較list1和list2中每一個(gè)節(jié)點(diǎn)，把較小的那個(gè)添加在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;
// 循環(huán)比較：
    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的下一個(gè)節(jié)點(diǎn)，把dummy排除
return dummy.next;
}
}

2. 遞歸思路:

設(shè)置一個(gè)根節(jié)點(diǎn)mergeNode，然后遞歸返回較小的節(jié)點(diǎn)

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