206. Reverse Linked List

# Definition for a binary Linked List
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverse_list(head):
    '''Iterative approach
    Time complexity : O(n)
    Space complexity : O(1)
    '''
    previous = None
    current = head
    while current:               #  None <-- n0 (prev)              //  current --> n2 --> n3 --> n4
        tmp = current.next       #  None <-- n0 (prev)              //  current --> n2 (tmp) --> n3 --> n4
        current.next = previous  #  None <-- n0 (prev) <-- current  //              n2 (tmp) --> n3 --> n4
        previous = current       #  None <-- n0 <-- current (prev)  //              n2 (tmp) --> n3 --> n4
        current = tmp            #  None <-- n0 <-- n1 (prev)       //          n2 (current) --> n3 --> n4
    return previous

def reverse_list(head):
    '''Recursive approach (a bit more subtle).

    the key is to work backwards.
    Assume that the rest of the list had already been reversed,
    now how do I reverse the front part?
    Let's assume the list is: n1 → ... → nk-1 → nk → nk+1 → ... → nm → Ø

    Assume from node nk+1 to nm had been reversed and you are at node nk.
    n1 → ... → nk-1 → nk → nk+1 ← ... ← nm
    We want nk+1’s next node to point to nk.
    So, nk.next.next = nk;

    Be very careful that n1's next must point to None.
    If you forget about this, your linked list has a cycle in it.
    This bug could be caught if you test your code with a linked list of size 2.

    Time complexity : O(n)
    Space complexity : O(n)  The extra space comes from implicit stack space due to recursion.
    '''
    if head is None or head.next is None:  # head == None just in case of empty list
        return head                        # head.next == None is the real base case (when p = head)

    p = reverse_list(head.next)
    # n0 --> _ --> nm-1  --> nm (head) --> None
    # n0 --> _ --> nm-1  --> nm (p = head) --> None
    # n0 --> _ --> nm-1  --> nm (p) --> None
    # n0 --> _ --> nm-1 <--> nm (p)
    # n0 --> _ --> nm-1 <--  nm (p)    (nm-1 --> None)
   
    #we end up with the following:   _ --> nk-1 -->  head  --> nk+1 <-- _ <-- nm (p)    (nk+1 --> None)
    head.next.next = head       #    _ --> nk-1 -->  head <--> nk+1 <-- _ <-- nm (p)    (nk+1 --> nk)
    head.next = None            #    _ --> nk-1 -->  head <--  nk+1 <-- _ <-- nm (p)    (head --> None)
    return p