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

插入法

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

/**
 * 
 * @param pHead1 ListNode类 
 * @param pHead2 ListNode类 
 * @return ListNode类
 */
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) 
{
    if(pHead1==NULL)
        return pHead2;
    if(pHead2==NULL)
        return pHead1;
    struct ListNode * t;
    struct ListNode * ans;
    if(pHead1->val>pHead2->val)
    {
        t=pHead1;
        pHead1=pHead2;
        pHead2=t;
    }
    ans=pHead1;
    while(pHead1->next&&pHead2)
    {
        if(pHead1->next->val>pHead2->val)
        {
            t=pHead2;
            pHead2=pHead2->next;
            t->next=pHead1->next;
            pHead1->next=t;
        }
        pHead1=pHead1->next;
    }
    if(pHead1->next==NULL)
        pHead1->next=pHead2;
    return ans;
}

迭代法(创建一个新链表)

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

/**
 * 
 * @param pHead1 ListNode类 
 * @param pHead2 ListNode类 
 * @return ListNode类
 */
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 )
{
    struct ListNode * cur;
    struct ListNode * result=(struct ListNode *)malloc(sizeof(struct ListNode));//创建一个新的头节点
    cur=result;
    while(pHead1&&pHead2)//这种方式要记住
   {
        if(pHead1->val<=pHead2->val) //哪个链表头节点小从哪个链表拿
            {
                cur->next=pHead1; //取节点
                pHead1=pHead1->next;//后移对应链表
            }
            else//同理
            {
                cur->next=pHead2;
                pHead2=pHead2->next;
            }
            cur=cur->next;//将新链表后移
   }
    if(pHead2==NULL) //将剩余的链表拼在后面（这个思路重点）
         cur->next=pHead1;
    if(pHead1==NULL)
         cur->next=pHead2;
        return result->next;
}