一、非递归实现

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(-1);
        ListNode cur = head;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        // 这里是当l1或者l2中至少有一个为null的时候，做剩余的处理
        // 比如：l2为null，l1不为null的时候
        // 那么说明l1剩下的节点的每个val都比l2最大的val还大
        // 则直接将cur.next置为l1，即将剩余的l1的节点直接放在cur的next
        // l1为null，l2不为null的时候同理
        if (l1 != null) {
            cur.next = l1;
        }
        if (l2 != null) {
            cur.next = l2;
        }
        return head.next;
    }

二、递归实现

    public ListNode mergeTwoLists1(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        // 判断，如果l1.val<=l2.val，则留下更小的，并且递归比较得到更小的这个节点的next
        // 先找到两个链表的头节点中更小的那个作为第一个节点
        // 然后进行递归依次找到剩下的节点，依次作为当前找到节点的next
        if (l1.val <= l2.val) {
            l1.next = mergeTwoLists1(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists1(l1, l2.next);
            return l2;
        }
    }