I have seen solutions to the reverse linked lists recursively but I dont understand the head.next.next part. Can someone explain this to me. This is leetcode 206 problem.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head
        curr = self.reverseList(head.next)
        head.next.next = head
        head.next = None
        return curr

When the recursive function reaches at the end and returns the last value of the list to curr, the next of curr and next of head is None right? So I feel the head.next.next should throw an error. Please explain this solution to me and why it isn't wrong.

CodePudding user response：

The recursive function will never reach the last value in the list and hence not throw an error. During recursion, the function takes in the node pointed by head.next, not the head itself. Hence the stopping condition is actually checking the condition: (if not head.next or not head.next.next).

Another way of looking at it is to consider what happens when the function is processing the (n-1)th node of an n-length list. The reverseList() function will take in the (n)th node - here head.next will be None, the program will return head and thus stop recursion.

CodePudding user response：

You should try walking through the code (in your head, or on paper, if that makes it easier) with a very short input, like ListNode(1, ListNode(2)).

With that input, the top-level function is very easy to understand. The head reference is to the 1 node, and head.next is the reference in that node to the 2 node. We could draw it like this:

head->1->2->None

head.next.next is the reference in the 2 node to whatever comes next, which for this input is None, since it's the end of the list.

When you assign to head.next.next, you're replacing that reference to None with a reference to the same node referred to by head (which is the 1 node), which makes a little loop in the linked list temporarily:

head->1->2
      ^   \
       \__/

However, we delete the link from the 1 node to the 2 node when we do head.next = None next, which breaks the loop and leaves us with only the reversed link from the 2 node to the 1 node. If we rearrange a bit, we have:

cur->2->1->None
        ^
       /
   head

As you can see, head in our code still points to the 1 node, so we don't want to return that, since it's not at the beginning of the reversed list. Instead we return cur, the value we got from the recursion, which is always going to be the last node from the original linked list (it is the 2 node in this case, but if we'd passed in a longer list it could have been several nodes away from our head and head.next stuff). That node is the head of the new reversed list.

CodePudding user response：

When the recursive function reaches at the end and returns the last value of the list to curr, the next of curr and next of head is None right?

The first claim is true. curr.next will be None, but the second claim is not true. head was not involved in the recursive call. The recursive call will reverse the shorter list that follows after head, but the head node itself is excluded from that process and so there is no way the recursive call could somehow modify head.next.

So I feel the head.next.next should throw an error.

It will not. The base case test at the top of the function guarantees that the recursive call is only made when head.next is not None. And since the recursive call has no way to alter head.next (as it doesn't have that head reference), this still is true when the recursive call returns.

It may help to visualise this with a list of 4 nodes.

head
  ↓
┌───────────┐   ┌───────────┐   ┌───────────┐   ┌───────────┐
│ val: 1    │   │ val: 2    │   │ val: 3    │   │ val: 4    │
│ next: ──────► │ next: ──────► │ next: ──────► │ next: None│
└───────────┘   └───────────┘   └───────────┘   └───────────┘

Now self.reverseList(head.next) is called, so that means the recursive call doesn't "see" the first node, but its successor. That node that is the start of a list with 3 nodes. This recursive call has its own head and curr names, which I will distinguish with an accent (as they really are local names). At the start of that recursive execution we have this state:

                 head'
                  ↓
                ┌───────────┐   ┌───────────┐   ┌───────────┐
                │ val: 2    │   │ val: 3    │   │ val: 4    │
                │ next: ──────► │ next: ──────► │ next: None│
                └───────────┘   └───────────┘   └───────────┘

Let's assume that this list is correctly reversed (we could go through all steps to prove that, but I will skip that process). That means that at the end of this recursive call a reference to the last node is returned, and the next references in these nodes have been updated, like so:

                 head'                           curr'
                  ↓                               ↓ 
                ┌───────────┐   ┌───────────┐   ┌───────────┐
                │ val: 2    │   │ val: 3    │   │ val: 4    │
                │ next: None│ ◄────── :next │ ◄────── :next │
                └───────────┘   └───────────┘   └───────────┘

The recursive call now ends, and returns the reference to the last node (curr') and the caller assigns that reference to its own curr name. This is the state for the caller:

head                                             curr
  ↓                                               ↓
┌───────────┐   ┌───────────┐   ┌───────────┐   ┌───────────┐
│ val: 1    │   │ val: 2    │   │ val: 3    │   │ val: 4    │
│ next: ──────► │ next: None│ ◄────── :next │ ◄────── :next │
└───────────┘   └───────────┘   └───────────┘   └───────────┘

Again, head was out of scope for the recursive call, so nothing changed to it: its next attribute remained as it was.

And now we get to the two last assignments which serve to attach the first node to the end of the reversed sublist. The tail of that reversed sublist is at head.next, and head.next.next = head will give us this result:

head                                             curr
  ↓                                               ↓
┌───────────┐   ┌───────────┐   ┌───────────┐   ┌───────────┐
│ val: 1    │┌► │ val: 2    │   │ val: 3    │   │ val: 4    │
│ next: ─────┘◄────── :next │ ◄────── :next │ ◄────── :next │
└───────────┘   └───────────┘   └───────────┘   └───────────┘

Finally, head.next is set to None, as this node has become the tail of the reversed list:

head                                             curr
  ↓                                               ↓
┌───────────┐   ┌───────────┐   ┌───────────┐   ┌───────────┐
│ val: 1    │   │ val: 2    │   │ val: 3    │   │ val: 4    │
│ next: None│ ◄────── :next │ ◄────── :next │ ◄────── :next │
└───────────┘   └───────────┘   └───────────┘   └───────────┘

Hope this clarifies it.