merge two sorted lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

合并两个已经排好序的链表，就跟合并两个排好序的数组一样，可以使用归并排序的思想。

第一种就是使用归并排序思想，不使用递归

  /*
    非递归，利用归并思想，合并时使用额外链表
    */
    /*
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        
        ListNode first=new ListNode(-1);  //用于返回的链表
        ListNode node=first;  //用于在first链表上移动
        
       
        if(l1==null) return l2;
        if(l2==null) return l1;
        
        while(l1!=null&&l2!=null){
            if(l1.val>l2.val){
　　　　　　　　　　
                node.next=l2;
                node=node.next; //这里不要忘记，不然只是在一个节点操作
                l2=l2.next;
            }else{
                node.next=l1;
                node=node.next;
                l1=l1.next;
            }
        }
        
    //这里需要，因为是在额外链表中操作的。
　　　　while(l1!=null){
            node.next=l1;
            node=node.next;
            l1=l1.next;
        }
        
        while(l2!=null){
            node.next=l2;
            node=node.next;
            l2=l2.next;
        }
        
        return first.next;
    }

归并，合并时不使用额外链表：

public ListNode merge(ListNode head1, ListNode head2)  
{  
    ListNode helper = new ListNode(0);  
    helper.next = head1;  //用l1作为结果集
    ListNode pre = helper;  
    while(head1!=null && head2!=null)  
    {  
        if(head1.val<head2.val)  
        {  
            head1 = head1.next;  
        }  
        else  //将小的元素插入到l1中
        {  
            ListNode next = head2.next;  
            head2.next = pre.next;  
            pre.next = head2;  
            head2 = next;  
        }  
        pre = pre.next;  
    }  
    while(head2!=null)  
    {  
        pre.next = head2;  
    }  
    return helper.next;  
}  

第二种方法，递归

 public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
         if(l1==null) return l2;
        if(l2==null) return l1;
         
         ListNode mergeNode;
         if(l1.val<l2.val){
             mergeNode=l1;
             mergeNode.next=mergeTwoLists(l1.next,l2);
         }else{
              mergeNode=l2;
             mergeNode.next=mergeTwoLists(l2.next,l1);
         }
         return mergeNode;
     }