将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

    示例 1：
    image.png

    输入：l1 = [1,2,4], l2 = [1,3,4]
    输出：[1,1,2,3,4,4]
    示例 2：

    输入：l1 = [], l2 = []
    输出：[]
    示例 3：

    输入：l1 = [], l2 = [0]
    输出：[0]

    提示：

    两个链表的节点数目范围是 [0, 50]
    -100 <= Node.val <= 100
    l1 和 l2 均按 非递减顺序 排列

    递归

    1. class Solution {
    2.     /**
    3.     因为排好序所以逐一比较就行，当list1.val < list2.val 就递归处理list1.next
    4.     与list2，然后返回list1即可，反之同理
    5.      */
    6.     public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    7.         if (list1 == null) return list2;
    8.         if (list2 == null) return list1;
    9.         if (list1.val < list2.val) {
    10.             list1.next = mergeTwoLists(list1.next,list2);
    11.             return list1;
    12.         }
    13.         list2.next = mergeTwoLists(list2.next,list1);
    14.         return list2;
    15.     }
    16. }

    迭代

    1. class Solution {
    2.     /**
    3.     因为排好序所以逐一比较就行，当list1.val < list2.val 就让cur.next指向它，当两个链表有一个为null时就退出循环，cur.next指向不是null的哪一个链表(如果都是null，无所谓指向哪一个)
    4.      */
    5.     public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    6.         ListNode dummy = new ListNode(0);
    7.         ListNode cur = dummy;
    8.         while (list1 != null && list2 != null) {
    9.             if (list1.val < list2.val) {
    10.                 cur.next = list1;
    11.                 list1 = list1.next;
    12.             } else {
    13.                 cur.next = list2;
    14.                 list2 = list2.next;
    15.             }
    16.             cur = cur.next;
    17.         }
    18.         cur.next = list1 == null ? list2 : list1;
    19.         return dummy.next;
    20.     }
    21. }
    26. class Solution {
    27.     /**
    28.     因为排好序所以逐一比较就行，当list1.val < list2.val 就让cur.next指向它，当两个链表有一个为null时就退出循环，cur.next指向不是null的哪一个链表(如果都是null，无所谓指向哪一个)
    29.      */
    30.     public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    31.         ListNode dummy = new ListNode(0);
    32.         ListNode cur = dummy;
    33.         while (list1 != null || list2 != null) {
    34.             if (list1 == null && list2 != null) {
    35.                 cur.next = list2;
    36.                 list2 = list2.next;
    37.             }
    38.             else if (list2 == null && list1 != null) {
    39.                 cur.next = list1;
    40.                 list1 = list1.next;
    41.             }
    42.             else if (list1.val < list2.val) {
    43.                 cur.next = list1;
    44.                 list1 = list1.next;
    45.             }
    46.             else {
    47.                 cur.next = list2;
    48.                 list2 = list2.next;
    49.             }
    50.             cur = cur.next;
    51.         }
    52.         return dummy.next;
    53.     }
    54. }