Reverse Linked List

作者: shaneZhang 分类: 算法与数据结构 发布时间: 2020-05-18 15:07
Method 1:

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        pre = None
        cur = head
        while cur:
            nexttmp = cur.next
            cur.next = pre
            pre = cur
            cur = nexttmp
        return pre

时间复杂度:O(n)
空间复杂度:O(1)
detail step is below the picture:
Method 2:
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next: return head

        p = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return p


时间复杂度:O(n)
空间复杂度:O(n)

detail step is below the picture:

如果觉得我的文章对您有用,请随意打赏。如果有其他问题请联系博主QQ(909491009)或者下方留言!

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注