Reverse Linked List

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: