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

/*
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) return pHead2;
		if(pHead2==nullptr) return pHead1;
	  
        ListNode* head, *p, *q, *r;
	  //选择pHead1,pHead2中头结点val较小的作为新链表的头结点，遍历另一个链表往里插数据
        if (pHead2->val > pHead1->val) {
            head = pHead1;
            p = pHead2;
        } else {
            head = pHead2;
            p = pHead1;
        }
        r = head;
        while (p != nullptr && r->next!=nullptr) {
            if (p->val >= r->val && p->val <= r->next->val) {//比r小比r->next大就插进去
                q = p->next;
                p->next = r->next;
                r->next = p;
                r = p;
                p = q;
            } else {
                r = r->next;
            }
        }
	  //若r遍历完了p还没遍历完，则说明剩下的p都比r大
		if(p!=nullptr) r->next = p;
        return head;
    }
};