合并两个有序链表（递归与非递归实现）

递归版本：

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

该方法如果理解不好，建议用追踪的方法，举个简单例子然后把递归的过程追踪出来。
非递归实现，思路和归并排序的merge过程一模一样，只不过变成操作链表。代码如下：

/********非递归版本***********/
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode Xhead = new ListNode(0);
        ListNode cur = Xhead;  //虚拟头节点，链表题目常用，可以少考虑很多情况。
        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                cur.next = new ListNode(l1.val);
                cur = cur.next;
                l1 = l1.next;
            }
            else{
                cur.next = new ListNode(l2.val);
                cur = cur.next;
                l2 = l2.next;
            }
            
        }
        while(l1 != null){
            cur.next = new ListNode(l1.val);
            cur = cur.next;
            l1 = l1.next;
        }
           while(l2 != null){
            cur.next = new ListNode(l2.val);
            cur = cur.next;
            l2 = l2.next;
        }
        return Xhead.next;
    }
}

新建一个辅助链表，谁小谁先进新链表，然后归并。