反轉(zhuǎn)鏈表-reverse linked list
假設(shè)存在鏈表 1 → 2 → 3 → ?，我們想要把它改成 ? ← 1 ← 2 ← 3。
在遍歷列表時(shí)，將當(dāng)前節(jié)點(diǎn)的 next 指針改為指向前一個(gè)元素。由于節(jié)點(diǎn)沒(méi)有引用其上一個(gè)節(jié)點(diǎn)，因此必須事先存儲(chǔ)其前一個(gè)元素。在更改引用之前，還需要另一個(gè)指針來(lái)存儲(chǔ)下一個(gè)節(jié)點(diǎn)。不要忘記在最后返回新的頭引用！
#非遞歸的形式
class
Solution
:
def
reverseList
(
self
,
head
:
ListNode
)
-
>
ListNode
:
cur
,
prev
=
head
,
None
while
cur
:
cur
.
next
,
prev
,
cur
=
prev
,
cur
,
cur
.
next
return
prev
復(fù)雜度分析
時(shí)間復(fù)雜度：O(n)，假設(shè) nn 是列表的長(zhǎng)度，時(shí)間復(fù)雜度是 O(n)。
空間復(fù)雜度：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
#別人的尾遞歸，無(wú)非就是記下前面的，和前面大同小異，但是運(yùn)行時(shí)間好像是快那么一點(diǎn)，不過(guò)這都不決定，因?yàn)閘eetccode的運(yùn)行時(shí)間提交多次的時(shí)間是不一樣的，所以不用那么糾結(jié)運(yùn)行時(shí)間，主要還是要分析好，時(shí)間復(fù)雜度。
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 官方解答已經(jīng)非常好了，就不重復(fù)造輪子了。
復(fù)雜度分析
時(shí)間復(fù)雜度：O(n)，假設(shè) nn 是列表的長(zhǎng)度，那么時(shí)間復(fù)雜度為 O(n)。
空間復(fù)雜度：O(n)，由于使用遞歸，將會(huì)使用隱式棧空間。遞歸深度可能會(huì)達(dá)到 n 層。
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺(jué)我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
