Python 反转链表-reverse linked list

系统 432 0

反转链表-reverse linked list

Python 反转链表-reverse linked list Leetcode No.206_第1张图片
假设存在链表 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 官方解答已经非常好了,就不重复造轮子了。
Python 反转链表-reverse linked list Leetcode No.206_第2张图片
复杂度分析

时间复杂度:O(n),假设 nn 是列表的长度,那么时间复杂度为 O(n)。
空间复杂度:O(n),由于使用递归,将会使用隐式栈空间。递归深度可能会达到 n 层。


更多文章、技术交流、商务合作、联系博主

微信扫码或搜索:z360901061

微信扫一扫加我为好友

QQ号联系: 360901061

您的支持是博主写作最大的动力,如果您喜欢我的文章,感觉我的文章对您有帮助,请请扫描上面二维码支持博主1元、2元、5元等您想捐的金额吧,狠狠点击下面给点支持吧

发表我的评论
最新评论 总共0条评论