链表反转（递归和非递归方式）的正确姿势

1、背景

关于链表的反转，很多资料讲解不够清晰，参考“无鞋童鞋”原文：

https://blog.csdn.net/fx677588/article/details/72357389

理解好了很多。

2、理论讲解

此部分内容引用自“

”

原文如下：

我们知道迭代是从前往后依次处理，直到循环到链尾；

而递归恰恰相反，首先一直迭代到链尾也就是递归基判断的准则，然后再逐层返回处理到开头。

总结来说，链表翻转操作的顺序对于迭代来说是从链头往链尾，而对于递归是从链尾往链头。

下面我会用详细的图文来剖析其中实现的细节。

迭代的方式是从链头开始处理，如下图给定一个存放5个数的链表。

首先对于链表设置两个指针：

然后依次将旧链表上每一项添加在新链表的后面，然后新链表的头指针NewH移向新的链表头，如下图所示。

此处需要注意，不可以上来立即将上图中P->next直接指向NewH，这样存放2的地址就会被丢弃，后续链表保存的数据也随之无法访问。

而是应该设置一个临时指针tmp，先暂时指向P->next指向的地址空间，保存原链表后续数据。

然后再让P->next指向NewH，最后P=tmp就可以取回原链表的数据了，所有循环访问也可以继续展开下去。