Given the head of a singly linked list, reverse the list, and return the reversed list.
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
Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?
## Solution(Python)
```Python
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
# 12345
# dummy -> cur
# while traversing list
# prev-> current cur -> cur.next
# prev <- cur <- cur.next
# cur.next = previous
# next_.next = cur
# prev = cur
# cur = cur.next
# simulation
# 1 2345
# prev = 1
# cur = 2
# -> 2
# 2.next = 1
# 3.next = 2
# prev = 2
# cur = 3
# 3
# 3.next = 2
# 4. next = 3
# prev = 3
# cur = 4
# 4
# 4.next = 3
# 5.next = 4
# prev = 4
# cur = 5
# corrected
# 1 2 3 4 5 None
# prev None
# cur
# prev cur next
# cur.next = prev
# prev = cur
# cur = next_
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
prev = None
cur = head
while cur:
next_ = cur.next
cur.next = prev
prev = cur
cur = next_
return prev
```