C++实现合并两个排序的链表

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;
    }
    // 把数值小的结点放入新链表，生成头节点
    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为合并后的头节点
      pHead1->next = Merge(pHead1->next, pHead2);
      return pHead1;
    }else{ // pHead2 为合并后的头节点
      pHead2->next = Merge(pHead1, pHead2->next);
      return pHead2;
    }
  }
};