首页 > 其他 > 详细

反转链表

时间:2020-09-22 22:57:20      阅读:20      评论:0      收藏:0      [点我收藏+]

标签:cpp   代码   img   链表   rgb   前驱   

  • 头插法反转链表

      所谓头插法反转链表就是在原来链表的基础上 依次将链表头部的结点摘下,然后从头部插入的方法生成一个新链表,则此链表为原来链表的逆转链表。

     算法步骤: 1:创建一个空链表表头

                                          技术分享图片

 

                    

                         2:摘取原链表的结点1,放在新空链表的表头后

 

                                           技术分享图片

 

 

                         3: 摘取原链表结点2,放在新链表头结点之后

                                                 技术分享图片

 

 

 

 

 

                          4:重复以上步骤,直到头结点的下一个结点(head->next) 为空

                                              技术分享图片

 

 

    

                                       实现了原链表的逆转,新链表结点的表头为new_head.

 

                  

//带头指针、头结点 
LinkList reserve(Linklist L)

{
    
    if(L->next==NULL){return NULL;}
    
    Linklist new_head = new   LNode ;//新链表的头指针
    while(L->next)  
    {
        
      /*插入新链表*/         
      new_head->next=L->next;    //将这个结点放在新链表头结点之后 
      
      /*删除L链表结点*/  
      L->next =L-> next->next;// L链表头结点之后的首元结点 ,换到下一个  
    } 
    
     return new_head;
}

 

 

  • 就地逆置法反转链表

    思路:对原链表进行修改, ○需要注意借助两个辅助指针

 

   step1:初试状

     首先 两个辅助指针指针p(工作指针)q(工作指针的后继指针),工作指针指向L->next,及首元结点,后继指针q指向L->next->next,即首元结点的下一个节点           目的:Prevetnt 断链

然后把原链表的头结点与后边链表断开来,因为首元结点已经赋给了p 工作指针 

  

LinkList p,q;
p = L->next; q =p->next;

L->next=NULL;

                                                                                                      技术分享图片

 

 

    Step2: 操作

   将后边后继指针(首元结点的next结点)所指结点拆下来,添加到当前头结点的后边 ,作为首元结点 。 [即2结点变为1结点前驱]

 

    代码思路如下:1) 剔除q结点    2结点

                             2) q结点挪到 链表头(作为首元结点)            2结点 挪到首元结点

                             3)  工作指针后移,后继指针后移

                                4) 循环

while(p)
{
    q=p->next; //工作指针后继
    p->next=q->next;//删除工作结点后结点
    
    q->next=L->next;//挪到首元结点 (L-> next) 
    L->next=q; 
    
    // 变换后继指针和工作指针 
     
}

 

 

 

 

技术分享图片

 

 

  

 

 

 

 

      两个方法的主要区别在于是否有新链表产生来接受,或者直接在原来链表实现。

 

反转链表

标签:cpp   代码   img   链表   rgb   前驱   

原文:https://www.cnblogs.com/chuanxuzhao/p/13714902.html

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号