## Description

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL


A linked list can be reversed either iteratively or recursively. Could you implement both?

## Solutions

### 1. Iterative

# Time: O(n)
# Space: O(n)
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if not node:
return pre
while node.next:
next = node.next
node.next = pre
pre = node
node = next
node.next = pre
return node

prev = None
curr.next = prev
prev = curr
return prev
# 27/27 cases passed (32 ms)
# Your runtime beats 81.2 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (14 MB)


### 2. Recursion

# Time: O(n)
# Space: O(n)
class Solution:
def reverseList(self, head: ListNode) -> ListNode:

def _reverse(self, node, pre=None):
if not node:
return pre
next = node.next
node.next = pre
return self._reverse(next, node)

# 27/27 cases passed (32 ms)
# Your runtime beats 81.31 % of python3 submissions
# Your memory usage beats 22.73 % of python3 submissions (18.6 MB)