Reverse a singly linked list.

**Example**:

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

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

**Follow up**:

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

## Solution

```
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if head == None:
return None
oldHead = head
newHead = head.next
oldHead.next = None
while newHead:
newHead2 = newHead.next
newHead.next = oldHead
oldHead = newHead
newHead = newHead2
return oldHead
```

## Test Cases

```
test = Solution()
testHead = ListNode(1)
testHead.next = ListNode(2)
testHead.next.next = ListNode(3)
answer = test.reverseList(testHead)
assert answer.val == 3
assert answer.next.val == 2
assert answer.next.next.val == 1
answer = test.reverseList(None)
assert answer == None
print('All Passed!')
```

## Big O Analysis

**Space Complexity**: O(1)

**Time Complexity**: O(N)