题目描述

解题思路

创建新节点

• 一个节点指向链表一，一个指向链表二，使用虚拟头节点在一个新链表上进行添加，根据 l1 和 l2 的大小判断进行添加。

• 最后有其中一个链表到尾后，另一个链表此时就可以把剩余的节点全部加在链表三上。

  /**
         * 新创建节点
         *
         * @param l1
         * @param l2
         * @return
         */
  public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1.next == null) {
        return l2;
    }
    if (l2.next == null) {
        return l1;
    }
    ListNode dummy = new ListNode(-1);
    ListNode cur = dummy;
    while (l1.next != null && l2.next != null) {
        if (l1.val > l2.val) {
            cur.next = l2;
            l2 = l2.next;
        } else {
            cur.next = l1;
            l1 = l1.next;
        }
        cur = cur.next;
    }
    if (l1.next == null) {
        cur.next = l2;
    } else {
        cur.next = l1;
    }
    return dummy.next;
  }

  递归法

  1、链表题，且有重复逻辑，一般都可以用递归。
  2、递归三部曲：

• 终止条件中，l1或者l2为空时，返回另一边，是常规操作了。关键是两边都不为空时，返回谁的问题。

• 返回值：在本层递归中，如果只是返回较小的节点，那么到最后的输出只有一个最后的节点。所以关键是怎么调用函数实现每次返回结果的连接，返回一个节点作为连接。
• 本层实现的逻辑：分析题目要求，递增合并链表，所以每一层向上返回的应该不仅是较小的节点，且该节点的后边为合并好的链表。所以先递归调用函数，完成当前节点和next节点（为下次递归的返回值）的连接，然后再返回当前节点。

  /**
         * 递归法
         *
         * @param l1
         * @param l2
         * @return
         */
  public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    if (l1 == null) {
        return l2;
    } else if (l2 == null) {
        return l1;
    } else {
        if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
  }