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