LeetCode 206. Reverse Linked List

'''
Reverse a singly linked list.
'''
class Solution(object):
   
    #24ms, 92.92%, 13.1MB, 26.08%
    def reverseList1(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        #try O(N) strorage
        l = []
        if not head: return None
        while head:
            l.append(head)
            head = head.next
        for i in range(-1, -len(l), -1):
            l[i].next = l[i-1]
        l[0].next = None
        return l[-1]

    #24ms, 12.8MB
    def reverseList2(self, head):
        #O(1) strorage
        if not head: return None
       
        p1 = head
        p2 = p1.next
        p1.next = None
        while p2:
            dump = p2
            p2 = p2.next
           
            dump.next = p1
            p1 = dump
       
        return p1

    #recursive, 24ms, 16.4MB
    def reverseList3(self, head):
        #recursive
        if not head or not head.next:
            return head
        else:
            dump = self.reverseList(head.next)
            head.next.next = head
            head.next = None
            return dump