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

示例：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

思路

代码的思路很明确，入参就是两个链表中需要比较的结点，如果说传入的某一个结点为空，则直接返回另一个入参结点即可，如果说传入的结点均不为空，则比较两个结点所带的数据的大小，将较小的结点返回，同时要注意到，代码中用到了递归，这点比较好理解，因为对于我们需要合并的某一个结点来说，完成一次合并后，其下一个结点，自然也能用相同的方法来找到，这样就找到了递归开始的条件，作为一个递归算法，还需要找到递归结束的条件，代码一开始的判断，如果说有一个入参为空，这说明已经到链表末尾，如果说两个入参均为空，这说明已经遍历完两个链表，整个递归结束，合并完成。

代码实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        
        ListNode resultNode = null;
        if (l1.val < l2.val) {
            resultNode = l1;
            resultNode.next = mergeTwoLists(l1.next, l2);
        } else {
            resultNode = l2;
            resultNode.next = mergeTwoLists(l1, l2.next);
        }
        
        
        return resultNode;
    }
}