import java.util.*;

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

public class Solution {
    /**
     * 代碼中的類名、方法名、參數(shù)名已經(jīng)指定，請勿修改，直接返回方法規(guī)定的值即可
     *
     * 
     * @param pHead1 ListNode類 
     * @param pHead2 ListNode類 
     * @return ListNode類
     */
    public ListNode Merge (ListNode pHead1, ListNode pHead2) {
        // 做一個頭節(jié)點占位
        ListNode res=new ListNode(0);
        //創(chuàng)建當前節(jié)點指針
        ListNode cur=res;
        //有一個鏈表為空的情況直接返回另一個列表
        if(pHead1==null){
            return pHead2;
        }else if (pHead2==null){
            return pHead1;
        }
        //其中有一個鏈表結(jié)束，循環(huán)就可以結(jié)束了，然后把另一個未結(jié)束的鏈表接入到合并鏈表的后面
        while(pHead1!=null&&pHead2!=null){
            //比較兩個鏈表當前節(jié)點值，較小的插入合并鏈表中，且該鏈表后移
            if(pHead1.val<=pHead2.val){
                cur.next=pHead1;
                pHead1=pHead1.next;

            }else{
                cur.next=pHead2;
                pHead2=pHead2.next;
            }
            //合并鏈表后移
            cur=cur.next;
        }
        //未結(jié)束的鏈表直接接入合并鏈表的后面
        cur.next=pHead2==null?pHead1:pHead2;
        
        //返回占位的頭節(jié)點的下一個節(jié)點，是真正數(shù)據(jù)的開始
        return res.next;
    }
}