目录

链表

反转链表

考虑先用递归实现。迭代思路虽然简单,但细节问题很多。

递归反转整个链表

代码如下:

https://narcissusblog-img.oss-cn-beijing.aliyuncs.com/uPic/file-09/ScreenShot2021-09-02%2014.23.10.png

对于递归算法,最重要的是明确递归函数的定义。reverseList函数的定义是:输入一个节点head,将head为起点的链表反转,并返回反转之后的头结点。

代码解释

对于如下的链表

https://narcissusblog-img.oss-cn-beijing.aliyuncs.com/uPic/file-09/ScreenShot2021-09-02%2014.27.37.png

输入reverseList(head)后,会在last := reverseList(head.Next)进行递归。执行完后,整个链表应该如下:

https://narcissusblog-img.oss-cn-beijing.aliyuncs.com/uPic/file-09/ScreenShot2021-09-02%2014.30.08.png

接下来的代码进行了如下操作,最后返回last。

https://narcissusblog-img.oss-cn-beijing.aliyuncs.com/uPic/file-09/ScreenShot2021-09-02%2014.32.10.pnghttps://narcissusblog-img.oss-cn-beijing.aliyuncs.com/uPic/file-09/ScreenShot2021-09-02%2014.32.18.png

这样整个链表就反转过来了。

注意:

1、递归函数需要base case,也就是下面的代码。

https://narcissusblog-img.oss-cn-beijing.aliyuncs.com/uPic/file-09/ScreenShot2021-09-02%2014.34.07.png

2、当链表递归反转之后,新的头结点是last,而之前的head变成了最后一个节点,因此需要指向nil。