• 头插法反转链表

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

     算法步骤： 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; 
    
    // 变换后继指针和工作指针 
     
}

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

反转链表

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