反转链表-reverse linked list
假设存在链表 1 → 2 → 3 → Ø，我们想要把它改成 Ø ← 1 ← 2 ← 3。
在遍历列表时，将当前节点的 next 指针改为指向前一个元素。由于节点没有引用其上一个节点，因此必须事先存储其前一个元素。在更改引用之前，还需要另一个指针来存储下一个节点。不要忘记在最后返回新的头引用！
#非递归的形式
class
Solution
:
def
reverseList
(
self
,
head
:
ListNode
)
-
>
ListNode
:
cur
,
prev
=
head
,
None
while
cur
:
cur
.
next
,
prev
,
cur
=
prev
,
cur
,
cur
.
next
return
prev
复杂度分析
时间复杂度：O(n)，假设 nn 是列表的长度，时间复杂度是 O(n)。
空间复杂度：O(1)。
#递归写法
class
Solution
:
def
reverseList
(
self
,
head
:
ListNode
)
-
>
ListNode
:
if
head
==
None
or
head
.
next
==
None
:
return
head
p
=
self
.
reverseList
(
head
.
next
)
head
.
next
.
next
,
head
.
next
=
head
,
None
#别人的尾递归，无非就是记下前面的，和前面大同小异，但是运行时间好像是快那么一点，不过这都不决定，因为leetccode的运行时间提交多次的时间是不一样的，所以不用那么纠结运行时间，主要还是要分析好，时间复杂度。
class
Solution
:
def
reverseList
(
self
,
head
:
ListNode
,
tail
=
None
)
-
>
ListNode
:
if
head
:
head
.
next
,
tail
,
head
=
tail
,
head
,
head
.
next
return
self
.
reverseList
(
head
,
tail
)
if
head
else
tail
Leetcode 官方解答已经非常好了，就不重复造轮子了。
复杂度分析
时间复杂度：O(n)，假设 nn 是列表的长度，那么时间复杂度为 O(n)。
空间复杂度：O(n)，由于使用递归，将会使用隐式栈空间。递归深度可能会达到 n 层。
