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

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */
/*
* 尾插
*/
void TailPushList(struct ListNode* ptHead, struct ListNode* ptNode) {
    struct ListNode* ptr = ptHead;
    while (ptr->next != NULL) {
        ptr = ptr->next;
    }
    ptr->next = ptNode;
    return ;
}

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param pHead1 ListNode类
 * @param pHead2 ListNode类
 * @return ListNode类
 */
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    struct ListNode *ptNewHead = (struct ListNode*)malloc(sizeof(struct ListNode));
    ptNewHead->next = NULL;
    ptNewHead->val = 0;
    struct ListNode *ptList1   = pHead1;
    struct ListNode *ptList2   = pHead2;
    struct ListNode *ptTmp     = NULL;
	
  	// 挨个进行比较，拆除小的，插入新的头结点
    while (ptList1 != NULL && ptList2 != NULL)      
    {
        if (ptList1->val >= ptList2->val)
        {
            ptTmp = ptList2;
            ptList2 = ptList2->next;   
        }
        else 
        {
            ptTmp = ptList1;
            ptList1 = ptList1->next;
        }
        ptTmp->next = NULL;
        TailPushList(ptNewHead, ptTmp);
    }
	// 把未到空的尾巴插入头结点
    ptTmp = (ptList1 == NULL) ? (ptList2) : (ptList1);
    TailPushList(ptNewHead, ptTmp);

    // 返回新的链表
    return ptNewHead->next;
}