Question: I wonder how to reverse a singly linked list using recursive approach in Python. This is LeetCode problem 206. Reverse Linked List:  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]  Most people use an iterative approach, which is quite classic and easily comprehensible. However, I have come across a recursive method which bewilders me: class Solution: def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: # recursive call if not head: return None newHead = head if head.next: newHead = self.reverseList(head.next) head.next.next = head head.next = None print(newHead) return newHead  For instance, if I input [1,2,3], I would manually work out the process as follows, which seems intuitively right but I cannot convince myself that it will return the right thing through recursive calls of reverselist. Can you kindly tell me why? Thanks very much! 

Answer: Here is how you could visualise the reversal of linked list 1→2→3: We start with:  head │ ┌─┴─────────┐ ┌───────────┐ ┌───────────┐ │ val: 1 │ │ val: 2 │ │ val: 3 │ │ next: ────────┤ next: ────────┤ next: None│ └───────────┘ └───────────┘ └───────────┘  The first recursive call receives head.next, and will have its own local names. To distinguish those local names from the names we alread have in the original execution of reverseList, I'll add accents to the names, where the number of acccents denotes the recursion depth. So at the first recursive call we can visualise the situation like this:  head head' │ │ ┌─┴─────────┐ ┌─┴─────────┐ ┌───────────┐ │ val: 1 │ │ val: 2 │ │ val: 3 │ │ next: ────────┤ next: ────────┤ next: None│ └───────────┘ └───────────┘ └───────────┘  And at the second level recursive call:  head head' head'' newHead'' │ │ │ │ ┌─┴─────────┐ ┌─┴─────────┐ ┌─┴──────┴──┐ │ val: 1 │ │ val: 2 │ │ val: 3 │ │ next: ────────┤ next: ────────┤ next: None│ └───────────┘ └───────────┘ └───────────┘  This second-level recursive execution will not enter the if block and just set the next attribute of head'' to None (which it already was) and return newHead''. Back to the first recursive execution that returned reference is assigned to newHead', so we have this:  head head' newHead' │ │ │ ┌─┴─────────┐ ┌─┴─────────┐ ┌─┴─────────┐ │ val: 1 │ │ val: 2 │ │ val: 3 │ │ next: ────────┤ next: ────────┤ next: None│ └───────────┘ └───────────┘ └───────────┘  In this recursive execution it is the first time we execute head.next.next = head, acting on head'. So we get:  head head' newHead' │ │ │ ┌─┴─────────┐ ┌─┴─────────┐ ┌─┴─────────┐ │ val: 1 │ │ val: 2 │ │ val: 3 │ │ next: ────────┤ next: ────────┤ next: ┐ │ │ │ │ ├───────────┘ │ └───────────┘ └───────────┘ └───────────┘  And then head' gets None for its next attribute:  head head' newHead' │ │ │ ┌─┴─────────┐ ┌─┴─────────┐ ┌─┴─────────┐ │ val: 1 │ │ val: 2 │ │ val: 3 │ │ next: ────────┤ next: None│ │ next: ┐ │ │ │ │ ├───────────┘ │ └───────────┘ └───────────┘ └───────────┘  Finally this first recursive execution returns newHead'. The original execution receives this reference and assigns it to its own newHead:  head newHead │ │ ┌─┴─────────┐ ┌───────────┐ ┌─┴─────────┐ │ val: 1 │ │ val: 2 │ │ val: 3 │ │ next: ────────┤ next: None│ │ next: ┐ │ │ │ │ ├───────────┘ │ └───────────┘ └───────────┘ └───────────┘  Again, head.next.next = head is executed:  head newHead │ │ ┌─┴─────────┐ ┌───────────┐ ┌─┴─────────┐ │ val: 1 │ │ val: 2 │ │ val: 3 │ │ next: ────────┤ next: ┐ │ │ next: ┐ │ │ ├───────────┘ ├───────────┘ │ └───────────┘ └───────────┘ └───────────┘  And finally, head.next is set to None and newHead is returned:  (returned) │ ┌───────────┐ ┌───────────┐ ┌─┴─────────┐ │ val: 1 │ │ val: 2 │ │ val: 3 │ │ next: None│ │ next: ┐ │ │ next: ┐ │ │ ├───────────┘ ├───────────┘ │ └───────────┘ └───────────┘ └───────────┘  ...which is the reversed list. Hope this clarifies it.