关于倒置链表的四种方法详解，总有一种适合你

单链表反转的四种方法

未反转的链表是这样的：

1、迭代反转法

简单点来说：迭代反转法的思路就是连续创立三个指针，beg、mid、end，遍历整个链表，在遍历期间，改变指针的指向，使他们指向前一个数据域。三个指针的最初指向与图一相同，具体做法与下面相同。

这里只需要改变mid的指针指向即可，，最后改变head的指针指向，使其与mid相同。

link * iteration_reverse(link* head) {
    if(head->next==NULL||head==NULL)
        return head;
    else
    {
        link * beg=NULL;
        link * mid=head;
        link * end=head->next;
        while(1)
        {
            mid->next=beg;
            if(end==NULL)
            {
                break;
            }
            beg=mid;
            mid=end;
            end=end->next;
           }
        head=mid;
        return head;
    }
}

2、递归反转链表

这种方法我也是学习了好久才学习明白的，所以先给大家奉上代码,并且进行注释之后再去进行讲解：

link* recursive_reverse(link* head) {
     if(head==NULL||head->next==NULL)//特殊情况的考虑
     {
     return head;
     }
     else
     {
     link * new_head=recursive_reverse(head->next);
     head->next->next=head;
     head->next=NULL;
     return new_head;
     }
}

1. 由于 head 不为 NULL，因此函数每执行到第 11 行时，递归都会深入一层，并依次将指向节点 2、3、4 的指针作为实参（head_next 的指向）参与递归。而根据递归出口的判断条件，当函数参数 head 指向的是节点 4 时满足 head->next == NULL，递归过程不再深入，并返回指向节点 4 的指针，这就是反转链表的新头指针。

因此，当递归首次退出一层时，new_head 指向的是节点 4 ，而 head 由于退出一层，指向的是节点 3，

2. 在此基础上，开始执行 17、18 行代码，整个操作过程如图 9 所示，最后将 new_head 的指向继续作为函数的返回值，传给上一层的 new_head。

3. 再退一层，此时 new_head 仍指向节点 4，而 head 退出一层后，指向的是节点 2。在此基础上执行 17、18 行代码，并最终将 new_head 的指向作为函数返回值，继续传给上一层的 new_head。

4. 再退一层，此时 new_head 仍指向节点 4，而 head 退出一层后，指向的是节点 1。在此基础上执行 17、18 行代码，并返回 new_head。（此方法不建议大家使用，废头发）图解如下：

3、头插法反转链表

所谓的头插法是指在链表的原有基础上，创立一个新的链表，依次将链表头部的节点拿下，置于新的链表头节点之后，此即为头插法。

下面就是关于头插法的图示讲解：

关于头插法的代码如下：

link * head_reverse(link * head) {
    link * new_head=NULL;
    link * temp=NULL;
    if(head==NULL||head->next==NULL)
    {
        return head;
    }
    while(head!=NULL)
    {
        temp=head;
        head=head->next;
        temp->next=new_head;
        new_head=temp;
    }
    return new_head;
}

4、就地逆置反转链表

此方法和头插法很相似，唯一的区别就在于此方法不用重新建立一个新的链表，而是直接的对于原来的链表进行修改，从而实现了对于链表的反转，但是需要额外借助两个指针

图解如下：

代码如下：

link * local_reverse(link * head) {
    link * beg=NULL;
    link * end=NULL;
    if(head==NULL||head->next==NULL)
    {
        return head;
    }
    else{
        beg=head;
        end=head->next;
    }
    while(end!=NULL)
    {
        beg->next=end->next;
        end->next=head;
        head=end;
        end=beg->next;
    }
    return head;
}

总结

本节仅以无头节点的链表为例，讲解了实现链表反转的 4 种方法。实际上，对于有头节点的链表反转：

• 使用迭代反转法实现时，初始状态忽略头节点（直接将 mid 指向首元节点），仅需在最后一步将头节点的 next 改为和 mid 同向即可；
• 使用头插法或者就地逆置法实现时，仅需将要插入的节点插入到头节点和首元节点之间即可；
• 递归法并不适用反转有头结点的链表（但并非不能实现），该方法更适用于反转无头结点的链表。

做这些花了我一个下午的时间，值不值得你为我点一波小小的关注，这么帅气的你点个赞再走呗