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

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
  public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
        auto vHead1 = new ListNode(1);
        vHead1->next = pHead1;
        auto vHead2 = new ListNode(1);
        vHead2->next = pHead2;
        auto nHead = new ListNode(1);
        ListNode* nTail = nHead;
        ListNode* p = NULL, *q = NULL;
        while (vHead1->next && vHead2->next) {
            p = vHead1->next;
            q = vHead2->next;
            if (p->val < q->val) {
                vHead1->next = p->next;
                p->next = NULL;
                nTail->next = p;
                nTail = p;
            } else {
                vHead2->next = q->next;
                q->next = NULL;
                nTail->next = q;
                nTail = q;
            }
        }
		if(vHead1->next)nTail->next=vHead1->next;
		if(vHead2->next)nTail->next=vHead2->next;
		return nHead->next;
    }
};