将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：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;
}
}
