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

//不清除重复变量 
/**  * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */

/**
 * 
 * @param pHead1 ListNode类 
 * @param pHead2 ListNode类 
 * @return ListNode类
 */
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    // write code here
    struct ListNode *first1 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode *first2 = (struct ListNode*)malloc(sizeof(struct ListNode));
    first1->next = pHead1;
    first2->next = pHead2;
    struct ListNode *p,*q;
    if(pHead1 == NULL || pHead2==NULL){
        if(pHead1 != NULL)
            return pHead1;
        if(pHead2 != NULL)
            return pHead2;
        return pHead1;
    }
    if(pHead1->val < pHead2->val){
        p=pHead1;q=pHead2;
        first1->next = pHead2;
        first2->next = pHead1;
    }
    else{
        p=pHead2;q=pHead1;
        first1->next = pHead1;
        first2->next = pHead2;
    }
    while(p->next!=NULL && first1->next!=NULL){        
        if(p->val <= q->val && p->next->val > q->val){
            first1->next = q->next;
            q->next = p->next;
            p->next = q;
            p=q;
            if(first1->next != NULL){
                q=first1->next;
            }
        }
        else if(p->next->val <= q->val){
            p=p->next;
        }        
        else{
            break;
        }
    }
    if(first1->next!=NULL){
        p->next=q;
    }
    p=first2->next;
    free(first2);
    return p;
    
    
    
}