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

1. 常规空检查
2. 依次合并，直到 任意一个链表为空
3. 将仍有剩余的一个链表附加在合并后的链表之后

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */
/**
 *
 * @param pHead1 ListNode类
 * @param pHead2 ListNode类
 * @return ListNode类
 */
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    // empty check
    if (!pHead1) {
        return pHead2;
    }

    if (!pHead2) {
        return pHead1;
    }
    // Note: we must pass 0 as default value here
    struct ListNode* head = 0;
    struct ListNode* p = 0;

    // loop and merge
    while (pHead1 && pHead2) {
        // find smaller
        struct ListNode* smaller = pHead1;
        if (pHead1 -> val > pHead2 -> val) {
            smaller = pHead2;
            pHead2 = pHead2->next;
        } else {
            pHead1 = pHead1 -> next;
        }
        // link
        if (!head) {
            p = head = smaller;
        } else {
            p->next = smaller;
            p = smaller;
        }
    }

    // append remains to tail
    if (pHead1) {
        p->next = pHead1;
    } else if (pHead2) {
        p->next = pHead2;
    }

    return head;
}