返回首页 / 程序员知识/如何实现单链表的反转

如何实现单链表的反转

2023-12-04 收藏 77

　　1、迭代反转链表：该算法的实现思想非常直接，就是从当前链表的首元节点开始，一直遍历至链表的最后一个节点，这期间会逐个改变所遍历到的节点的指针域，另其指向前一个节点。具体的实现方法也很简单，借助 3 个指针即可。

　　2、递归反转链表：和迭代反转法的思想恰好相反，递归反转法的实现思想是从链表的尾节点开始，依次向前遍历，遍历过程依次改变各节点的指向，即另其指向前一个节点。该方法的实现用到了递归算法，不易理解。

　　3、头插法反转链表：所谓头插法，是指在原有链表的基础上，依次将位于链表头部的节点摘下，然后采用从头部插入的方式生成一个新链表，则此链表即为原链表的反转版。

　　4、就地逆置法反转链表：就地逆置法和头插法的实现思想类似，唯一的区别在于，头插法是通过建立一个新链表实现的，而就地逆置法则是直接对原链表做修改，从而实现将原链表反转。值得一提的是，在原链表的基础上做修改，需要额外借助 2 个指针。

赞同101
应用指南

猜你喜欢