# Problem

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

# Solution

## Recursive

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
"""
:rtype: ListNode
"""
# time: O(n) memory O(n)
# basecase
# recrusive action, we repeatedly call reverseList with head.next
# because of how recursive actions work we will be at the last node when we
# "unwind", aka we will go backwards when we execute code after node =....
# Instead of recursing the entire linked list we will recurse the remainder of the linked list
# this creates a sub-problem, we now only have N - 1 nodes to deal with.
# We break it down even more and say "recurse all apart from head.next" so we get N - 2 nodes to deal with
# and so on.
# When the above line finishes, it returns the head of the reversed list (which is the last node in the original list). When you do original_last_node.next it points to None, since it's the last node in the original list.
# head.next.next = head appends the original head to the end of the reversed list (the true end)
# **original list**
# node -> ... -> head.next -> None
# Return node
# Since we recurse down to the last node, we only have NODE_X to access so we cannt point it back to the previous node in a singly linked list
# therefore we keep it pointing at None
# So when we finally finish up we need to clean up the mess we made lolsies

return node


## Iterative

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
"""
:rtype: ListNode
"""
# time: O(n) memory O(1)
# The idea is that we iterate through the list and set the previous node to the node 1 befire
# our current node
# we then set our current node to point at our previous node
# so we reverse the list in place
prev = None