Recursive 1, going from head to tail
The recursive call takes two argument, prev and curr that points to previous and current nodes we are working with. We assume/know that all the nodes before and at prev is already reversed and we will just reverse the current pointer to point at reverse. After the current is reversed, we move on to the next recursive reverse with prev = curr and curr = the original curr next.
The base case is when curr is None, that means we have reached the None terminator. So the prev must point at the last node and all the nodes before the last node is already reversed. So we just return the pointer to the last node, which is assigned to prev.
The last node’s pointer got propagated returned back to the top of call stack and is eventually returned to the main.
def reverse(prev, curr): if not curr: return prev next_node = curr.next curr.next = prev return reverse(curr, next_node) new_head = reverse(None, head) return new_head
Recursive 2, going from tail to head
In this case, the recursive function has 1 argument, curr, the pointer to the node we are working with. During each call of the recursive function, we assume everything after curr has been reversed. So we need to point the curr.next’s next pointer to curr. Then we also need to point curr.next to Null. We can think that at every level of recursive call, the function assume the current is the last node and need to “clean up” by adding a Null. It also prevents cycles.
def reverseList(self, head): """ :type head: ListNode :rtype: ListNode """ def reverse(curr): if curr.next == None: return curr new_head = reverse(curr.next) curr.next.next = curr curr.next = None return new_head if not head: return None new_head = reverse(head) return new_head
In the while loop, we will reverse one node at a time and point it to the previous node.
def reverseList(self, head): """ :type head: ListNode :rtype: ListNode """ prev = None curr = head while curr != None: next_node = curr.next curr.next = prev prev = curr curr = next_node return prev
We will iterate till the current node is at Null and return the previous node.
I first had:
def reverseList(self, head): """ :type head: ListNode :rtype: ListNode """ prev = None curr = head while curr.next != None: next_node = curr.next curr.next = prev prev = curr curr = next_node return curr
Doesn’t deal with empty list
If the linked list is empty, then the head will be None and None doesn’t has .next
The while loop will terminate at the last node instead at the Null node. This will let the last node’s next not be updated to pointing at its predecessor node.