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

/**
 * 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
    struct ListNode *head, *head1, *head2, *tmp1, *tmp2;
    if(pHead1 == NULL)
        return pHead2;
    if(pHead2 == NULL)
        return pHead1;
    if (pHead1->val < pHead2->val)
    {
        head1 = pHead1;
        head2 = pHead2;
        //printf("pHead1->val=%d\n", pHead1->val);
    }
    else
    {
        head1 = pHead2;
        head2 = pHead1;
        //printf("pHead2->val=%d\n", pHead2->val);
    }
    head = head1;
    while(head2 != NULL)
    {
        while(head1 != NULL)
        {
            if(head1->next == NULL)
            {
                head1->next = head2;
                return head;
            }
            else
            {
                if(head1->next->val > head2->val)
                {
                    tmp1 = head1->next;
                    tmp2 = head2->next;
                    head1->next = head2;
                    head2->next = tmp1;
                    head2 = tmp2;
                    head1 = head1->next;
                    break;
                }
                else
                    head1 = head1->next;
            }

        }

    }
    return head;

}