<svg xmlns="http://www.w3.org/2000/svg" style="display: none;"> <path stroke-linecap="round" d="M5,0 0,2.5 5,5z" id="raphael-marker-block" style="-webkit-tap-highlight-color: rgba(0, 0, 0, 0);"></path> </svg> <p></p> 讯享网
链表是面试里面经常涉及到的考点，因为链表的结构相比于 、、 或者图等数据结构简单许多，对于后者更多面试的侧重点在于其底层实现。比如 中 等操作、如何扩容、容量的设定等。链表的考察更侧重于代码的书写和思路的形成。虽然说，链表的结构简单，但是涉及到指针的操作，容易引申出一些挑战性的考题，其中也牵涉到诸多小的细结的考虑，更能看出代码书写的能力和功底。
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
链表的存取从头指针（）开始，头指针表示链表中第一个结点的存储位置。同时由于最后一个结点没有后续数据，则线性链表中最后一个结点的指针为“空”（）。
反转链表，又可以称为翻转或逆置链表，它们表达的是同一个意思。把上图所示的有序链表反转后，得到新的有序链表。
常用的实现链表反转的方案有四种，这里分别将它们称为迭代反转法、递归反转法、头插法和原地逆置法。
关于链表的增删改查问题，我在另一篇博客《【面试分享】嵌入式面试题常考难点之关于单链表的增删改查》中做了详细的讨论，欢迎有需要的小伙伴查阅。
从当前链表的第一个结点开始遍历整个链表，期间逐个改变所遍历的结点的指针域，令其指向前一个结点。具体实现方法需要借助三个结点指针，如下图，分别把三个指针命名为 、、。
遍历链表的过程就是三个指针一起向链表结尾逐步偏移，直到 指针指向 为止。这个过程中，由指针改变它所指向的结点的指针域，令其指向所指向的结点。如下图：
最后只需改变头指针的指向，令其和同向，就实现了链表的反转。
代码实现如下：
讯享网
运行结果：
递归反转法的实现思想是从链表的尾结点开始，依次向前遍历，遍历过程依次改变各结点的指向，即令其指向前一个结点。这种方法一般会在函数中建立一个新的头指针，通过层层递进的方式找到链表尾结点，然后将新的头指针指向尾结点，再层层返回把每个遍历后的结点都指向上一个结点，最后令原先的头结点指向 ，使其成为链表反转后，新链表的尾结点，并返回新的头指针。
代码实现如下：
头插法一般用于链表的创建，这里用的头插法大致相同，就是将原链表的结点从链表头逐个取下，并用头插法创建链表的方式重新建立一个反向排序的链表，已达到反转链表的效果。具体做法如下图：
代码实现如下：
讯享网
这个方法和头插法类似，区别在于头插法是通过摘除旧的结点重新排列成新的链表，而原地逆置法则是直接对原链表做修改。这就需要借助两个结点指针进行链表结点的标记，再通过遍历链表逐个逆置结点。具体过程如下图：
代码实现如下：
- 使用迭代反转法实现时，初始状态忽略头结点（直接将 指向首元结点），仅需在最后一步将头结点的 改为和 同向即可；
- 使用头插法或者原地逆置法实现时，仅需将要插入的结点插入到头结点之前即可；
- 递归法并不适用反转有头结点的链表（但并非不能实现），该方法更适用于反转无头结点的链表。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/142154.html