###### tags: `learning` `algorithm` `leetcode` `linked list`

# Reverse a linked list, recursive

ref = https://www.geeksforgeeks.org/reverse-a-linked-list/

I tried to translate the following code of cpp to Python 3.

    Node* reverse(Node* head) 
    { 
        if (head == NULL || head->next == NULL) 
            return head; 
  
        /* reverse the rest list and put  
          the first element at the end */
        Node* rest = reverse(head->next); 
        head->next->next = head; 
  
        /* tricky step -- see the diagram */
        head->next = NULL; 
  
        /* fix the head pointer */
        return rest; 
    } 

## Method #0

class LinkedList:
    def reverse(self, node):
        # the condition to stiop the recurrence 
        if node == None or node.next == None: 
            # node == None is for empty l-lists
            # node.next == None is for non-empty l-lists, 
            # it is the point of bouncing-back, bottum of recurrence
            return node
        newHead = self.reverse(node.next)
        # newhead is the last node of the original linked-list
        node.next.next = node    
        node.next = None
        return newHead

code
https://github.com/y56/proving-ground/blob/master/reverse-a-linked-list/recursive-method0.py
to print
https://github.com/y56/proving-ground/blob/master/reverse-a-linked-list/recursive-method0-print.py
the print-out
https://github.com/y56/proving-ground/blob/master/reverse-a-linked-list/recursive-method0-print.out

- input l-list:
1 -> 2 -> 3 -> 4 -> null
- After reverse(4), the recurrence is stopped and the algorithm bounces back.
- The recursive process will stop at the end of the l-list.
- The recursive part is to find the tail.
- As the algorithm bouncing back, it will rearrange the linkage of nodes, from tail to head.
- The deepest recursive layer will trigger

if node == None or node.next == None: 
    return node

and return the pointer of the tail node.
- Then, when going back, the pointer will be passed back, until passed to

myLinkedList.head = myLinkedList.reverse(myLinkedList.head)

and become the new head.

- We shall use `myLinkedList.head = myLinkedList.reverse(myLinkedList.head)` instead of `myLinkedList.head = myLinkedList.reverse()`.

- Or, we can package `myLinkedList.head = myLinkedList.reverse(myLinkedList.head)` in something like

def purelyMethodStyleReverse():
    myLinkedList.head = myLinkedList.reverse(myLinkedList.head)