反轉(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 層。