# 206. Reverse Linked List

# 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):
def reverseList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
# time: O(n) memory O(n)
if not head or not head.next:
# basecase
return head
# 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
# from the head
# 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.
node = self.reverseList(head.next)
# 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**
# head -> head.next -> head.next.next -> ... -> node
# **node = self.reverseList(head.next)**
# node -> ... -> head.next -> None
# Return node
# node -> ... -> head.next -> head -> None
# 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
head.next.next = head
head.next = None
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):
def reverseList(self, head):
"""
:type head: ListNode
: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
while head:
curr = head
head = head.next
curr.next = prev
prev = curr
return prev
```