题解 | #合并两个排序的链表#

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pHead1 ListNode类
     * @param pHead2 ListNode类
     * @return ListNode类
     */
    public ListNode Merge (ListNode pHead1, ListNode pHead2) {
        // write code here

        if (null == pHead1 && null == pHead2) {
            return null;
        }
     
        ListNode newList = new ListNode(0);
        recursiveCompare(pHead1, pHead2, newList);
        return newList;
    }
    void recursiveCompare(ListNode n1, ListNode n2, ListNode newList) {
	  
	  /*注意地址变化的问题 newList=n1,不等同与
	  newList.val = n2.val;
            newList.next = n2.next;
			前者会将newList的地址直接换成n1的地址，
	
	  */
        if (null == n1 && null == n2) {
         return;  
        }
        if (null == n1 ) {
            newList.val = n2.val;
            newList.next = n2.next;
            return;  
     
        }
        if (null == n2 ) {
             newList.val = n1.val;
             newList.next = n1.next;
             return;  
    
        }

        if (n1.val <= n2.val) {
            newList.val = n1.val;
            newList.next = new ListNode(0);
            recursiveCompare(n1.next, n2, newList.next);
        } else {
            newList.val = n2.val;
            newList.next = new ListNode(0);
            recursiveCompare(n1, n2.next, newList.next);
        }    
    }


}