归并排序链表

/*
 * 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.
 */
public class MergeTwoSortedList {
	class ListNode {
		      int val;
		      ListNode next;
		      ListNode(int x) {
		          val = x;
		         next = null;
		      }
	}
	  public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
	        // Start typing your Java solution below
	        // DO NOT write main() function
	        if( l1 == null) return l2;
	        if( l2 == null) return l1;
	        
	        ListNode head = null;
	        ListNode other = null;
	        if(l1.val<l2.val) {head = l1; other = l2;}
	        else{ head = l2; other = l1;}
	        
	        ListNode resultPrev = head;
	        ListNode resultCur = resultPrev.next;
	        ListNode otherPtr = other;
	        
	        while(resultCur!=null&&otherPtr!=null){
	            if(resultCur.val<=otherPtr.val) {
	                resultPrev = resultPrev.next;
	                resultCur = resultCur.next;
	            }
	            else{
	                resultPrev.next = otherPtr;
	                otherPtr = resultCur;
	                resultCur = resultPrev.next;
	            }
	        }
	        if(resultCur == null) resultPrev.next = otherPtr;
	        
	        
	        return head;
	    }
}