[数据结构与算法]有序链表的合并

?一开始的思路：

????????大体上是对的，但是太浪费空间，每次去create一个新node，用类似于归并排序里面的逐一比较，依次放到newList中，最终也观察到有头链表print的时候，要置为NULL，选择了逐一去销毁->太浪费空间和时间。

解决办法:

????????就直接用指针逐一将目标结点依次有序串联起来，无需去copy相同的结点，最终记得将L1->Next=NULL;L2->Next=NULL;

遇到的问题：

????????段错误

? ? ? ? ? ? ? ? 访问越界了，一开始L1->Next=NULL;L2->Next=NULL;写成了p1->Next=NULL但实际上，p1作为移动指针已经移动到最后了，不能访问Next!!!

最初的代码——>臃肿且有bug

PtrToNode createNode(int data)
{
    PtrToNode newNode=(PtrToNode)malloc(sizeof(struct Node));
    newNode->Data=data;/*有头*/
    newNode->Next=NULL;
    return newNode;
}
void push_back(List list,int data)
{
    if(list==NULL)return ;
    PtrToNode pos=createNode(data);
    PtrToNode pMove=list->Next;
    while(pMove->Next)
    {
        pMove=pMove->Next;
    }
    pMove->Next=pos;
}
List Merge( List L1, List L2 )
{
    if(L1==NULL&&L2==NULL)return NULL;
    if(L1==NULL)return L2;
    if(L2==NULL)return L1;
    List newList=()malloc(sizeof(struct Node));
    //初始化  
    newList->Next=NULL;
    PtrToNode p1=L1->Next;/*有头链表*/
    PtrToNode p2=L2->Next;
    
   while(p1&&p2)//有点个像归并排序->两者必须都要存在
   {
       if(p1->Data<p2->Data)
       {//不为空的时候再去
           push_back(newList,p1->Data);
           p1=p1->Next;
       }
       else
       {
            push_back(newList,p2->Data); 
            p2=p2->Next;
       } 
   }
    while(p1)
    {
        push_back(newList,p1->Data);
        p1=p1->Next;
    }
    while(p2)
    {
        push_back(newList,p2->Data);
        p2=p2->Next;
    }
    //销毁原来的链表
    for(p1=L1,p2=L2;p1||p2;)
    {
        if(p1)
        {
            PtrToNode t=p1->Next;
            free(p1);
            p1=t;
        }
        if(p2)
        {
            PtrToNode t=p2->Next;
            free(p2);
            p2=t;
        }
    }
    return newList;
}

修改后：

? ? ? ? 注意一点：和归并排序逐一比较之后不太一样的一点是->没有再去while逐一放入newList中，直接用链表串联起来即可。

List Merge( List L1, List L2 )
{
    if(L1==NULL)
    {
        if(L2==NULL||L2->Next==NULL)return NULL;
        else if(L1->Next==NULL)return L2;
        else return L1;
    }
    List newList=(List)malloc(sizeof(struct Node));
    //初始化  
    //newList->Next=NULL;//注：newList的作用:始终保存头结点
    List p=newList;//pmove
    PtrToNode p1=L1->Next;/*有头链表*/
    PtrToNode p2=L2->Next;  
   while(p1&&p2)//有点个像归并排序->两者必须都要存在
   {
       if(p1->Data<p2->Data)
       {//不为空的时候再去
           p->Next=p1;
           p1=p1->Next;
       }
       else
       {
            p->Next=p2;
            p2=p2->Next;
       } 
       p=p->Next;
   }
    if(p1)//优化
    {
        p->Next=p1;
    }
    if(p2)
    {
        p->Next=p2;//优化后的结果
    }
    L1->Next=NULL;//一开始错写成:p1->Next==NULL会导致访问越界。
    L2->Next=NULL;
    return newList;
}

?reference：

02-线性结构1 两个有序链表序列的合并　　题目要求实现一个函数，将两个链表表示的递增整数序列合并为一个非递减的整数序列。　　这道题较为基础，主要考察C语言中链表的基本操作。只要会“连接”链表，考虑清楚比较过程和前后关系不难想出思路，关键是http://www.west999.com/info/html/chengxusheji/C-C--/20180618/4195557.html