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

struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
ListNode *merge(ListNode *p, ListNode *q)
{
    ListNode *head = p, *pre, *temp, *k1 = NULL,*k2 = NULL;
    //k1,k2为判断标志，pre为p的前一节点，temp做临时变量，head记录初始位置
    while (p != NULL && q != NULL)
        {
            if (p->val > q->val)//插在pre，p中间
            {
                if (pre == k1)//当相等时，避免重复插入，更新pre
                    pre = pre->next;
                temp = q->next;//保留q的下一位   
                pre->next = q;//将pre指向q
                q->next = p;//将q指向p
                q = temp;//更新q
                k1 = pre;//更新k1
            }
            else if(p->val == q->val)//相等时 将q插入p后面
            {
                if(p == k2)//当相等时，避免重复插入，更新p
                    p = p->next;
                temp = q->next; //保留q的下一位               
                q->next = p->next;//将q指向p->next
                p->next = q;//p指向q
                q = temp;//更新q
                k2 = p;//更新k2
            }
            else
            {
                pre = p;
                p = p->next;
            }//当小于时，更新pre和p
        }
        if (p == NULL)
            pre->next = q;//当p为先空时，将pre接到q链表上
    
    return head;//返回头结点
}
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2) 
    {
        struct ListNode *p = pHead1, *q = pHead2,*r;//p，q代替链表初始位置，r为最终结果
        if (!p)
            return q;//当p为空时，返回q
        if (!q)
            return p;//同上
        if(p->val < q->val)
            r = merge(p,q);//根据首元素的大小判断，最终第一个链表p还是q
        else
            r = merge(q,p);
        
        return r;        //返回结果
    }
};