Linked List - Reverse a linked list

"""
https://leetcode.com/problems/reverse-linked-list/description/

Given the head of a singly linked list, reverse the list, and return the reversed list.

2024.08.21
- Ok I think the way I remembered how to do this is useful for the future. The first line of code
that I wrote in the function was `current.next = prev`, which is IMO the core of the algorithm, where you're flipping
around the order of the connections.
- That line of code reminded me that I need to have `current` and `prev` variables. The next line of code I wrote was
`prev = current`, because that's the other core of the algorithm IMO, the step forward.
- I then saw that I would clearly need to update the `current` variable, which would be the current node's original
`.next`, but since I was changing it with the `current.next = prev` line, I'd need to save a reference to the original
node. So I wrote the `current = _next` line followed by the `_next = current.next` line.
- The rest is easy, I just added the `while current:`, the initial `current = ` and `prev = `, and it was clear that
`prev` would have a reference to the final node in the original list (which becomes the head node in the reordered
list).
"""

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next


# Iterative solution
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        current = head
        prev = None
        while current:
            _next = current.next
            current.next = prev
            prev = current
            current = _next
        return prev


# Recursive solution

"""
The `head is None` check is just handling the single edge-case of getting passed zero nodes at the beginning (i.e. empty input). If any nodes at all are passed in the original function, that check should never get reached, as the recursion will end at the `head.next is None` check first. This is important to understand because it's how we can be sure that the recursive function will return an actual node as the head of the reversed list instead of None (which would seem to be the natural endpoint for recursively looking at the .next property in a linked list).

I think the `head.next.next = head` line is the key trick to remember for this function.
"""

class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head.next is None or head is None:
            return head

        head_of_reversed_list = self.reverseList(head.next)
        head.next.next = head
        head.next = None

        return head_of_reversed_list