## 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:

- Advance the
`next`

pointer to the next node - Reverse the
`curr.next`

pointer so that it points back to`prev`

- Advance the
`prev`

pointer to`curr`

- 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:

- 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. - 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. - We will then reverse the pointer
`head.next.next = head`

- We will set
`head.next`

=`None`

to avoid cycles - 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
curr = head
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]:
if not head or not head.next:
return head
else:
node = self.reverseList(head.next)
head.next.next = head
head.next = None
return node
```