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.

Naive Way: A usual way is to treat it like merging two sorted arrays.

 /**  
  * Definition for singly-linked list.  
  * public class ListNode {  
  *   int val;  
  *   ListNode next;  
  *   ListNode(int x) {  
  *     val = x;  
  *     next = null;  
  *   }  
  * }  
  */  
 public class Solution {  
   public ListNode mergeTwoLists(ListNode l1, ListNode l2) {  
     ListNode fake = new ListNode(0);  
     ListNode cur = fake;  
     while(l1 != null && l2 != null){  
       if(l1.val < l2.val){  
         cur.next = l1;  
         l1 = l1.next;  
       }else{  
         cur.next = l2;  
         l2 = l2.next;  
       }  
       cur = cur.next;  
     }  
     if(l1 != null) cur.next = l1;  
     if(l2 != null) cur.next = l2;  
     return fake.next;  
   }  
 }  

Improved way: There is a better to make use a queue structured recursive method.

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