反轉鏈表-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)，由于使用遞歸，將會使用隱式?？臻g。遞歸深度可能會達到 n 層。
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
