请问链表的问题中如何实现单向和双向链表的反转

Question

请问链表的问题中如何实现单向和双向链表的反转

Answer 1

提问者 zzl1998 2018-11-25 10:52:06

感谢老师的解答，非常详细，您的课程很好

Answer 2

liuyubobobo 2018-11-25 02:10:29

链表的反转是一个经典问题。Leetcode的206号问题就是链表的反转。

传送门：

英文版：https://leetcode.com/problems/reverse-linked-list/

中文版：https://leetcode-cn.com/problems/reverse-linked-list/

在我的《玩转算法面试》课程中，详细的分析了这个问题。有兴趣的话可以参考，也可以直接参考我的代码：

非递归算法：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0206-Reverse-Linked-List/java-0206/src/Solution1.java

递归算法：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0206-Reverse-Linked-List/java-0206/src/Solution2.java

对于非递归算法，通过循环，每次翻转相邻两个节点的指向。代码看似简单，但对链表表不熟练，很容易写错，强烈建议根据代码，用纸笔绘制出每次pre和cur都指向着谁，相应的pre和cur的next又是如何变化的：）

对于递归算法，相应好理解的多。但前提是对递归本身理解的比较深刻。强烈建议首先理解这个课程中，以删除链表为例子，所介绍的递归的宏观语义和微观语义。之后，再以链表反转为例，加深一下这个理解，无论是宏观语义还是微观语义：）

（我的代码中，ListNode reverseList(ListNode head)的语义是：反转以head为头结点的链表，返回翻转后的链表的头结点。）

如果理解了单链表的反转，实现双链表的反转近乎是完全一样的。只不过对于每一个节点，除了处理next，还要处理prev而已。其实通常面试中很少考察双链表的翻转。不过有兴趣，可以在彻底理解单链表翻转的基础上，自己试试看？：）

加油！：）