链表
目录
反转链表
考虑先用递归实现。迭代思路虽然简单,但细节问题很多。
递归反转整个链表
代码如下:
对于递归算法,最重要的是明确递归函数的定义。reverseList函数的定义是:输入一个节点head
,将以head
为起点的链表反转,并返回反转之后的头结点。
代码解释
对于如下的链表
输入reverseList(head)
后,会在last := reverseList(head.Next)
进行递归。执行完后,整个链表应该如下:
接下来的代码进行了如下操作,最后返回last。
这样整个链表就反转过来了。
注意:
1、递归函数需要base case,也就是下面的代码。
2、当链表递归反转之后,新的头结点是
last
,而之前的head
变成了最后一个节点,因此需要指向nil。