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

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

/**
 * 
 * @param pHead1 ListNode类 
 * @param pHead2 ListNode类 
 * @return ListNode类
 */

void setNode(struct ListNode *q, int val);

void setNode(struct ListNode *q, int val) {

    q->val = val;
    q->next = NULL;
}
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    // write code here
    struct ListNode *head = NULL;
    struct ListNode *p1 = NULL;
    struct ListNode *p2 = NULL;
    struct ListNode *q;
    struct ListNode *h = NULL;

    if(pHead1 == NULL) {
        return pHead2;
    }
    if(pHead2 == NULL) {
        return pHead1;
    }

    for(p1 = pHead1,p2=pHead2;p1&&p2;) {
        q = (struct ListNode*)malloc(sizeof(struct ListNode));
        if(p1->val < p2->val) {
            setNode(q,p1->val);
            p1 = p1->next;
        }
        else {
            setNode(q,p2->val);
            p2 = p2->next;
        }
        if(head == NULL) {
            head = q;
        }
        else {
            h->next = q;
        }
        h = q;
    }

    if(p1 != NULL) {
        for(;p1; p1 = p1->next) {
            q = (struct ListNode*)malloc(sizeof(struct ListNode));
            setNode(q,p1->val);
            h->next = q;
            h = q;
        }
    }

    if(p2 != NULL) {
        for(;p2; p2 = p2->next) {
            q = (struct ListNode*)malloc(sizeof(struct ListNode));
            setNode(q,p2->val);
            h->next = q;
            h = q;
        }
    }

    return head;
}