## Problem Statement#

### Description#

Given the head of a singly linked list, reverse the list, and return the reversed list.

### Examples#

#### Example 1:#

``````Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]
``````

#### Example 2:#

``````Input: head = [1,2]
Output: [2,1]
``````

#### Example 3:#

``````Input: head = []
Output: []
``````

### Constraints#

• The number of nodes in the list is the range `[0, 5000]`
• `-5000 <= Node.val <= 5000`

## Key Insights#

In order to reverse a singly linked list iteratively, you need to use three pointers: `prev`, `curr` and `next`. The following algorithm can be used:

1. Advance the `next` pointer to the next node
2. Reverse the `curr.next` pointer so that it points back to `prev`
3. Advance the `prev` pointer to `curr`
4. Advance the `curr` pointer up to `next`
flowchart LR z((prev=Ø))-.-a((curr=1))-.-b((next=2))-->c((3))-->d((4))-->e((5)) a-->z

In order to reverse a singly linked list recursively, we will need to be very careful to ensure that we don’t end up with any cycles. The following algorithm can be used:

1. For each recursive call, check if `head` or `head.next` is `None` and return `head` if either are. If `head is None`, we know that we don’t have a linked list and we need to exit. If `head.next is None`, we know that we have either reached the end, or we have successfully broken the link between the `head` and the next node.
2. Once the previous two conditions have passed, we will recursively call `reverseList(head.next)` to drill down to the end of the list. Once we reach the end, `(head.next).next` will be `None`, and it will return return `head.next` up one stack frame.
3. We will then reverse the pointer `head.next.next = head`
4. We will set `head.next` = `None` to avoid cycles
5. Finally, we will return the node from the previous call up the call stack. Once we return back to the first call, the returned result will be the original tail node that is now the new head node.

## Python Solution#

### Iterative Solution#

``````# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
prev = None
next = None

while curr:
next = curr.next
curr.next = prev
prev = curr
curr = next

return prev
``````

### Recursive Solution#

``````# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: