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

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

/**
 * 
 * @param pHead1 ListNode类 
 * @param pHead2 ListNode类 
 * @return ListNode类
 */
 //思路：
 //第一种情况：pHead1是空，返回pHead1
 //第二种情况：pHead2是空，返回pHead2
 //第三种情况：
 //方法一是新建一个结点，往后接新链表，需要两个新指针
 //方法二是先比较大小，确定好初始节点，用两个新指针同时指向初始节点，一个保持不变，一个指向新链表的最后节点，用于拓展节点
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 )
 {
    // write code here
    //第一种情况：pHead1是空，返回pHead1
    if (pHead1 == NULL)
     {
        return pHead2;    
    }

    //第二种情况：pHead2是空，返回pHead2
    if (pHead2 == NULL)
     {
        return pHead1;
    }

    //第三种情况：
    //方法一是新建一个结点，往后接新链表，需要两个新指针
    //一个指针不断向后移动接节点，一个保持不变用于导出新链表
    struct ListNode *pHead = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode *p = pHead;
    p->next = NULL;

    //遍历比较两个链表，任意其中一个链表为空就退出
    while(pHead1 != NULL && pHead2 != NULL)
    {
        if(pHead1->val < pHead2->val)
        {
            p->next = pHead1;   //接上新节点
            p = p->next;    //指针p向后移动，为下次接新节点作准备
            pHead1 = pHead1->next;  //就链表向后移动
            p->next = NULL;     //将尾节点的next置空
        }
        else
        {
            p->next = pHead2;
            p= p->next;
            pHead2 = pHead2->next;
            p->next = NULL;
        }
    }

    //当有相对较长的链表时，就挂到新链表的尾节点上
    if(pHead1 != NULL)
    {
        p->next = pHead1;   //拼接
    }

    if(pHead2 != NULL)
    {
        p->next = pHead2;
    }

    return(pHead->next);
}