算法学习之合并两个有序链表

题目：

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

示例：

输入：1->2->5, 0->3->4

输出：0->1->2->3->4->5

实现思路：

我们可以如下递归地定义在两个链表里的 merge 操作（忽略边界情况，比如空链表等）：

{ 
list1[0]+merge(list1[1:],list2)
list2[0]+merge(list1,list2[1:])
?	
  
list1[0]<list2[0]
otherwise
?	

也就是说，两个链表头部较小的一个与剩下元素的 merge 操作结果合并。

算法：

我们直接将以上递归过程建模，首先考虑边界情况。

特殊的，如果 l1 或者 l2 一开始就是 null ，那么没有任何操作需要合并，所以我们只需要返回非空链表。否则，我们要判断 l1 和 l2 哪一个的头元素更小，然后递归地决定下一个添加到结果里的值。如果两个链表都是空的，那么过程终止，所以递归过程最终一定会终止。

如下是图解：

递归实现如下：

/**
 * 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 || l2 == null){
         return l1!=null?l1:l2;
     }
     if(l1.val <l2.val){
         l1.next = mergeTwoLists(l1.next,l2);
         return l1;
     }
     else{
         l2.next = mergeTwoLists(l1,l2.next);
         return l2;
     }
}
}