# Leetcode 206. Reverse Linked List

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

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

Input: head = []
Output: []

**Note:
There are two solutions. Should know both very well.**

## Iterative Solution:
* Time Complexity: O(n)
* Space Complexity: O(1)

# 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, curr = None, head
        
        while curr:
            next = curr.next
            curr.next = prev
            prev = curr
            curr = next
            
        return prev

**Key: Two Pointers**

1. initiate two pointers(prev -> null, curr -> head)
2. start iteration (while curr:)
3. store curr.next address to variable named "next"
4. move curr.next points to prev
5. prev move to curr
6. curr move to the address previously stored in "next"
7. after iteration, **curr will point at null and prev will become the new head.** So just return prev will be the answer.

## Recursion Solution:
* Time Complexity: O(n)
* Space Complexity: O(n): call stacks

**Key:**
**1. head.next.next = head**
**2. Base case: head == None or head.next == None**

**延伸：**
1. 如果base case只有if not head會發生甚麼事情：AttributeError, NoneType object as no attribute next
2. 如果base case只有if not head.next會發生甚麼事情：Same with above

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        
        # Base Case
        if not head or not head.next:
            return head
        
        reversed_head = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        
        return reversed_head

The stack frames visualized before popping out

Use the following code to visualize. Will have a better understanding than explaining in words

Notes:
**1. reversed_head will always be the last node(5)**
2. head.next = None is meant to be letting the previous node to point to null. e.g. 5->4->None, and at the mean time 3(head) is also pointing to 4.

https://pythontutor.com/visualize.html#mode=edit

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
        
class Solution:
    def reverseList(self, head):
        # base case
        if not head  or not head.next:
            return head
        
        last = self.reverseList(head.next)
        head.next.next = head
        head.next = None

        return last
        
solution = Solution()
node = ListNode(1)
node.next = ListNode(2)
node.next.next = ListNode(3)
node.next.next.next = ListNode(4)
node.next.next.next.next = ListNode(5)
node.next.next.next.next.next = None

solution.reverseList(node)