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

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
	  //cur用与保存每次循环用来比较的值，比如第一次循环，1和2进行比较，1小，将1挂载到-1后面，cur从-1变为1
	  //这方便了将2挂载到1这个节点上，以此类推，可将两个链表合并成一个新的链表
        ListNode cur = new ListNode(-1);
	  //用于返回新链表的，这个新链表挂载在-1上，所以最后返回sen.next
        ListNode sen = cur;
	  //循环比较两个链表
        while(pHead1!=null&&pHead2!=null){
            if(pHead1.val<=pHead2.val){
                cur.next=pHead1;
                pHead1 = pHead1.next;
            }else{
                cur.next = pHead2;
                pHead2 = pHead2.next;
            }
            cur = cur.next;
        }
	  //循环结束时，可能会有一个链表还有剩余的节点。我们需要将剩余的节点全部接到 cur 的后面
        if(pHead1!=null)
            cur.next = pHead1;
        if(pHead2!=null)
            cur.next = pHead2;
        return sen.next;
    }
}