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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

/**
 * 
 * @param pHead1 ListNode类 
 * @param pHead2 ListNode类 
 * @return ListNode类
 */
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    // write code here   
    int flag;
    struct ListNode *p = pHead1;
    struct ListNode *q = pHead2;
    struct ListNode *temp;

    if(pHead1 == NULL && pHead2 != NULL)
    {
        return pHead2;
    }
    else if(pHead1 != NULL && pHead2 == NULL)
    {
        return pHead1;
    }
    else if(pHead1 == NULL && pHead2 == NULL)
    {
        return NULL;
    }

    struct ListNode *head;
    if(p->val > q->val)
    {
        head = q;
        q = q->next;
        flag = 1;
    }
    else {
        head = p;
        p = p->next;
        flag = 0;
    }

    while(1)
    {
        if(p == NULL){
            head->next = q;
            break;
        }

        if(q == NULL){
            head->next = p;
            break;
        }

        if(p->val > q->val)
        {
            temp = q->next;
            head->next = q;
            q->next = p;
            q = temp;
        }
        else {
            temp = p->next;
            head->next = p;
            p->next = q;
            p = temp;
        }
        head = head->next;        
    }

    if(flag)
    {
        return pHead2;
    }else{
        return pHead1;
    }

}