struct ListNode {
  int val;
  struct ListNode *next;
  ListNode(int x) :
  val(x), next(NULL) {
  }
};

class Solution {
public:
  ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
  {
    ListNode* newList = NULL; //新鏈表頭
    ListNode* newListRear = NULL; //新鏈表尾
    // 先處理某個鏈表為空的情形
    if (pHead1 == NULL){
      return pHead2;
    }
    if (pHead2 == NULL){
      return pHead1;
    }
    // 把數(shù)值小的結(jié)點放入新鏈表，生成頭節(jié)點
    if (pHead1->val <= pHead2->val){
      newList = pHead1;
      newListRear = pHead1;
      pHead1 = pHead1->next;
    }else{
      newList = pHead2 ;
      newListRear = pHead2;
      pHead2 = pHead2->next;
    }
    // 兩表均不空的情形下，遍歷 
    while (pHead1 != NULL && pHead2 != NULL) {
      if (pHead1->val <= pHead2->val) {
        newListRear->next =pHead1;
        newListRear = pHead1;
        pHead1 = pHead1->next;
      }else{
        newListRear->next =pHead2;
        newListRear = pHead2;
        pHead2 = pHead2->next;
      }
    }
    //某一表為空時，把另一表接入新表表尾 
    if (pHead1 == NULL) {
      newListRear->next = pHead2;
    }
    if (pHead2 == NULL) {
      newListRear->next = pHead1;
    }
    
    return newList;
  }
};

class Solution {
public:
  ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
  {
    if (pHead1 == NULL){
      return pHead2;
    }
    if (pHead2 == NULL){
      return pHead1;
    }
    
    if (pHead1->val <= pHead2->val){ // pHead1為合并后的頭節(jié)點
      pHead1->next = Merge(pHead1->next, pHead2);
      return pHead1;
    }else{ // pHead2 為合并后的頭節(jié)點
      pHead2->next = Merge(pHead1, pHead2->next);
      return pHead2;
    }
  }
};