从无到有算法养成篇-线性表实战篇

实战一：题⽬1 将2个递增的有序链表合并为⼀个有序链表; 要求结果链表仍然使⽤两个链表的存储 空间,不另外占⽤其他的存储空间. 表中不允许有重复的数据

例如：
La {1,2,3} , Lb {3, 6,9}
Lc {1, 2, 3, 6, 9}

 
1、递增有序链表代表：插入适合后插，前插会倒序；
2、表中不允许有重复的数据：合并各表前无重复数据，合并后也无重复数据，需要进行删除操作；
3、不另外占⽤其他的存储空间：无须建立新链表。

 
1、定义4个指针，Pa 和 Pb 分别是La,Lb的工作指针，初始化分别为对应的首元节点，合并后的新表使用头指针Lc(Lc的表头结点设为La的表头结点)指向，temp用来记录重复节点，以便后面进行释放；
2、因为合并后的为递增有序链表，所以需要从首元结点开始比较循环比较，循环结束条件是两个链表La 和Lb 有一个到达表尾结点时，即代码判断是否为空；循环体内进行比较，比较两个节点的元素，pc 指向较小的节点，无须释放，当相等时，我们默认指向 pa，并对 pb 进行释放，以免造成重复数据;
3、当结束循环时，把非空链表剩余部分链接至Lc表后面；
4、释放Lb的头结点。

代码块参考：

  

   

    

     

    
    

     

      void MergeList(LinkList *La, LinkList *Lb, LinkList *Lc){
     
    
   

    

     

    
    

     

         LinkList pa,pb,pc,temp;
     
    
   

    

     

    
    

     

         pa = (
     
    
  
 

文章来源: wenyusuran.blog.csdn.net，作者：文宇肃然，版权归原作者所有，如需转载，请联系作者。

原文链接：wenyusuran.blog.csdn.net/article/details/107706009