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

其实做过了，不过这次不用首元结点解决的 差别不大，先判断出取哪一个作为第一个结点（以此代替首元结点）

/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
      if (pHead1 == nullptr || pHead2 == nullptr) {
         return pHead1 == nullptr ? pHead2 : pHead1;
      } 
      
      ListNode *head = pHead1->val < pHead2->val ? pHead1 : pHead2;
      ListNode *list1, *list2;
      list1 = head->next;
      list2 = head == pHead1 ? pHead2 : pHead1;
      ListNode *cur_head = head;
      
      while (list1 && list2) {
        if (list1->val < list2->val) {
          cur_head->next = list1;
          list1 = list1->next;
        } else {
          cur_head->next = list2;
          list2 = list2->next;
        }
        cur_head = cur_head->next;
      }
      
      cur_head->next = list1 == nullptr ? list2 : list1;
      
      return head;
    }
};