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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pHead1 ListNode类 
 * @param pHead2 ListNode类 
 * @return ListNode类
 */
/*
思维逻辑：
题目我将它定义为插入，那么链表节点的插入有头插、中间插入、尾部插入三种；
然后针对大于等于和小于时情况，分析头部插入、中间插入、尾部插入的情况。
犯错总结
	1、在头部时赋值头指针的时候写错了，错把tail=pHead1写成了pHead1=tail
	2、在考虑比较大小的时候忘记了小于号、
	3、忽略了只有一个节点时也是满足tail==pHead1&&head==pHead1的。条件语句有所遗漏
	
学习总结：
1、比起我这种直接修改指针进行插入，其实最好的应该是创建一个新的链表头指针，对在这两个增序链表直接对比，选择节点值小的加入到新链表里：
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    // write code here
    struct ListNode* dummyHead=malloc(sizeof(struct ListNode));
    struct ListNode* cur=dummyHead;
    while(pHead1!=NULL&&pHead2!=NULL){
        if(pHead1->val<=pHead2->val){
            cur->next=pHead1;
            pHead1=pHead1->next;
        }else{
            cur->next=pHead2;
            pHead2=pHead2->next;
        }
        cur=cur->next;
    }
    cur->next=pHead1==NULL?pHead2:pHead1;
    return dummyHead->next;
*/
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    // write code here
    struct ListNode *head=pHead1;
    struct ListNode *tail=pHead1;
    struct ListNode *goal=pHead2;
    struct ListNode *tmp=NULL;
    while(goal!=NULL&&pHead1!=NULL)//链表都不为空
    {
        //头部
        if(tail==pHead1&&head==pHead1&&tail->next!=NULL)
        {
            if(goal->val<tail->val)
            {
                //头部插入
                tmp=goal;
                goal=goal->next;
                tmp->next=pHead1;
                pHead1=tmp;
                head=pHead1;
                tail=pHead1;
            }else {
                if(pHead1->next!=NULL)
                tail=pHead1->next;
            }
        }
        else if(tail!=head)//中间插入
        {
            if(goal->val<=tail->val)//插入
            {   tmp=goal;
                goal=goal->next;
                head->next=tmp;
                tmp->next=tail;
                //head移动
                head=head->next;
                
            }else {
                head=head->next;
                if(tail->next!=NULL)
                {tail=tail->next;}
            }
        }else//尾部插入
        {
            if(goal->val>tail->val)//移动
            {
                tail->next=goal;//将剩余的尾部全部接入headp1链表
                goal=NULL;
            }
        }
        
       
    }
    return pHead1;


}