how do I trace through a recursion to reverse a linked list?

user_16349825 0
Viewed 153

I have some recursive code that reverses linked lists:

#We are dealing with ListNodes.

def reverseList(head):
    
    if not head or not head.next:
        return head
    second = head.next
    reverse = reverseList(second)
    second.next = head
    head.next = None

    return reverse

I am struggling to follow the code on paper, here is what I understand for say input 1->2->3->4:

head = 1 
second = head.next = 2 
reverse = reverseList(second=2) 
second = 3 
reverse = reverseList(second=3) 
second = 4
reverse = reverseList(second=4) 

since head.next = None, return head (=4) 

second.next(=None) = 4
... and I am so confused.

Am I tracing through the recursion correctly?

recursion linked-list python
1 Answers

To represent the nodes as mere numbers will not help much to understand the algorithm. It is essential that head, second and reverse are node references, and that each recursive call of the function, has its own, distinct set of variables -- even though their names are the same as in another call.

To get better insight, imagine a numeric suffix to each variable, in order to differentiate them according to the execution context they are defined in. So the top level call will have head1, second1, reverse1, and the first recursive call will have its own head2, second2, reverse2, ...etc.

Let's visualise the list at the moment second has been initialised:

     head1            second1
      ↓                ↓
    ┌───────────┐    ┌───────────┐    ┌───────────┐    ┌───────────┐
    │ value: 1  │    │ value: 2  │    │ value: 3  │    │ value: 4  │
    │ next: ———————→ │ next: ———————→ │ next: ———————→ │ next:None │
    └───────────┘    └───────────┘    └───────────┘    └───────────┘

Now the recursive call is made, passing it the reference to the second node. In the recursive execution context, this reference is named head, and we also get a new second reference:

                      head2            second2
                       ↓                ↓
    ┌───────────┐    ┌───────────┐    ┌───────────┐    ┌───────────┐
    │ value: 1  │    │ value: 2  │    │ value: 3  │    │ value: 4  │
    │ next: ———————→ │ next: ———————→ │ next: ———————→ │ next:None │
    └───────────┘    └───────────┘    └───────────┘    └───────────┘

A similar set of variables gets assigned in the next recursive execution context:

                                       head3            second3
                                        ↓                ↓
    ┌───────────┐    ┌───────────┐    ┌───────────┐    ┌───────────┐
    │ value: 1  │    │ value: 2  │    │ value: 3  │    │ value: 4  │
    │ next: ———————→ │ next: ———————→ │ next: ———————→ │ next:None │
    └───────────┘    └───────────┘    └───────────┘    └───────────┘

The deepest recursive call will have its head referencing the last node:

                                                        head4
                                                         ↓  
    ┌───────────┐    ┌───────────┐    ┌───────────┐    ┌───────────┐
    │ value: 1  │    │ value: 2  │    │ value: 3  │    │ value: 4  │
    │ next: ———————→ │ next: ———————→ │ next: ———————→ │ next:None │
    └───────────┘    └───────────┘    └───────────┘    └───────────┘

This deepest call returns head. The caller (which has its own set of variables), assigns that return value to reverse

                                                        reverse3 = head4
                                       head3            second3
                                        ↓                ↓
    ┌───────────┐    ┌───────────┐    ┌───────────┐    ┌───────────┐
    │ value: 1  │    │ value: 2  │    │ value: 3  │    │ value: 4  │
    │ next: ———————→ │ next: ———————→ │ next: ———————→ │ next:None │
    └───────────┘    └───────────┘    └───────────┘    └───────────┘

Then second.next = head and head.next = None get executed:

                                                        reverse3
                                       head3            second3
                                        ↓                ↓
    ┌───────────┐    ┌───────────┐    ┌───────────┐    ┌───────────┐
    │ value: 1  │    │ value: 2  │    │ value: 3  │    │ value: 4  │
    │ next: ———————→ │ next: ———————→ │ next: None│ ←——————— :next │
    └───────────┘    └───────────┘    └───────────┘    └───────────┘

This call comes to an end, and returns reverse to the caller. The caller has its own variables, and assigns the returned reference to their reverse variable:

                      head2            second2          reverse2 = reverse3 
                       ↓                ↓                ↓
    ┌───────────┐    ┌───────────┐    ┌───────────┐    ┌───────────┐
    │ value: 1  │    │ value: 2  │    │ value: 3  │    │ value: 4  │
    │ next: ———————→ │ next: ———————→ │ next: None│ ←——————— :next │
    └───────────┘    └───────────┘    └───────────┘    └───────────┘

Then second.next = head and head.next = None get executed:

                      head2            second2          reverse2
                       ↓                ↓                ↓
    ┌───────────┐    ┌───────────┐    ┌───────────┐    ┌───────────┐
    │ value: 1  │    │ value: 2  │    │ value: 3  │    │ value: 4  │
    │ next: ———————→ │ next: None│ ←——————— :next │ ←——————— :next │
    └───────────┘    └───────────┘    └───────────┘    └───────────┘

This call comes to an end, and returns reverse to the caller. The caller has its own variables, and assigns the returned reference to their reverse variable:

     head1            second1                           reverse1 = reverse2 
      ↓                ↓                                 ↓
    ┌───────────┐    ┌───────────┐    ┌───────────┐    ┌───────────┐
    │ value: 1  │    │ value: 2  │    │ value: 3  │    │ value: 4  │
    │ next: ———————→ │ next: None│ ←——————— :next │ ←——————— :next │
    └───────────┘    └───────────┘    └───────────┘    └───────────┘

Then second.next = head and head.next = None get executed:

     head1            second1                           reverse1 
      ↓                ↓                                 ↓
    ┌───────────┐    ┌───────────┐    ┌───────────┐    ┌───────────┐
    │ value: 1  │    │ value: 2  │    │ value: 3  │    │ value: 4  │
    │ next: None│ ←——————— :next │ ←——————— :next │ ←——————— :next │
    └───────────┘    └───────────┘    └───────────┘    └───────────┘

This call comes to an end, and returns reverse to the caller. This is indeed the new head of the completely reversed list.

user_54598390
Related