21. 合并两个有序链表
题目链接：
解题思路：
遍历，双指针：因为两个链表有序，所以只需要依次比较两个元素的大小，然后添加到新的链表中即可
first指针指向第一个链表l1，second指针指向第二个链表l2，answer保存合并后的链表的头节点的前驱，prev初值指向answer
如果fist和second当前指向的节点都不为null，循环遍历：
如果first.val<second.value，prev.next=first，first=first.next，prev=prev.next
否则，prev.next=second，second=second.next，prev=prev.next
循环结束之后，那么first和second只会有一个节点不为null，因为原链表已经有序，所以只需要将不为null的哪个链表添加到prev.next中即可
最终answer.next即所求
AC代码：
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {ListNode first = list1;ListNode second = list2;ListNode head = new ListNode();ListNode tem = head;while (first != null && second != null) {if (first.val < second.val) {tem.next = new ListNode(first.val);first = first.next;tem = tem.next;} else {tem.next = new ListNode(second.val);second = second.next;tem = tem.next;}}tem.next = first != null ? first : second;return head.next;}
}
递归解法
对于递归解法，首先需要定义递归函数的功能，然后定义递归的终止条件
递归函数mergeTwoLists(ListNode list1, ListNode list2)：表示返回list1和list2有序合并之后的新链表的头节点
递归的终止条件：
如果其中任何一个链表为null，那么直接返回剩余的一个链表就可以了
否则：进行递归求解
如果list1.val<list2.val，这个时候list1就是合并后有序链表的头节点。也就是说递归函数返回的结果应该为list1，但是list1后面的节点和list2还没有合并，所以还不能直接返回list1，返回之前需要保证list1.next的值是list1后面的节点和list2合并之后的有序链表的头节点，这样list1才是满足结果的链表的头节点，查看递归函数的定义，经过mergeTwoLists(list.next,list2)后，list.next和list2也已经有序合并，并且递归函数的返回值就是list.next和list2有序合并后新链表的头节点，因此list1.next=mergeTwoLists(list.next,list2)，然后return list1
否则，合并后有序链表的头节点为list2，list2.next的值就是list1和list2.next合并后有序链表的头节点，因此list2.next=mergeTwoLists(list, list2.next)，然后return list2
AC代码
class Solution {public ListNode mergeTwoLists(ListNode list1, ListNode list2) {if (list1==null){return list2;}else if (list2==null){return list1;}else {if (list1.val< list2.val){list1.next=mergeTwoLists(list1.next,list2);return list1;}else {list2.next=mergeTwoLists(list1,list2.next);return list2;}}}
}