链表是面试里面经常涉及到的考点，因为链表的结构相比于 、、 或者图等数据结构简单许多，对于后者更多面试的侧重点在于其底层实现。比如 中 等操作、如何扩容、容量的设定等。链表的考察更侧重于代码的书写和思路的形成。虽然说，链表的结构简单，但是涉及到指针的操作，容易引申出一些挑战性的考题，其中也牵涉到诸多小的细结的考虑，更能看出代码书写的能力和功底。
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
链表的存取从头指针（）开始，头指针表示链表中第一个结点的存储位置。同时由于最后一个结点没有后续数据，则线性链表中最后一个结点的指针为“空”（）。
反转链表，又可以称为翻转或逆置链表，它们表达的是同一个意思。把上图所示的有序链表反转后，得到新的有序链表。
常用的实现链表反转的方案有四种，这里分别将它们称为迭代反转法、递归反转法、头插法和原地逆置法。
关于链表的增删改查问题，我在另一篇博客《【面试分享】嵌入式面试题常考难点之关于单链表的增删改查》中做了详细的讨论，欢迎有需要的小伙伴查阅。
从当前链表的第一个结点开始遍历整个链表，期间逐个改变所遍历的结点的指针域，令其指向前一个结点。具体实现方法需要借助三个结点指针，如下图，分别把三个指针命名为 、、。
最后只需改变头指针的指向，令其和同向，就实现了链表的反转。
代码实现如下：
运行结果：
递归反转法的实现思想是从链表的尾结点开始，依次向前遍历，遍历过程依次改变各结点的指向，即令其指向前一个结点。这种方法一般会在函数中建立一个新的头指针，通过层层递进的方式找到链表尾结点，然后将新的头指针指向尾结点，再层层返回把每个遍历后的结点都指向上一个结点，最后令原先的头结点指向 ，使其成为链表反转后，新链表的尾结点，并返回新的头指针。
代码实现如下：
代码实现如下：
代码实现如下：
- 使用迭代反转法实现时，初始状态忽略头结点（直接将 指向首元结点），仅需在最后一步将头结点的 改为和 同向即可；
- 使用头插法或者原地逆置法实现时，仅需将要插入的结点插入到头结点之前即可；
- 递归法并不适用反转有头结点的链表（但并非不能实现），该方法更适用于反转无头结点的链表。
版权声明：
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！
转载请注明出处，原文链接：https://www.xkablog.com/cjjbc/51376.html