Why does my reverse linked list function mutate the global variable linkedlist?-CodePudding

The following is my code:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

    def __str__(self):
        return str(self.val)   " -> "   str(self.next)

def reverse_list(head: ListNode) -> ListNode:
    prev, curr  = None, head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

linked_list = ListNode(1, ListNode(2, ListNode(3)))

When printed out, linked_list is displayed as "1 -> 2 -> 3 -> None". However, after calling the function reverse_list once, and then printing linked_list again, it seems to be mutated and became 1 -> None. Could anyone explain the reasoning behind this? Example shown below:

print(linked_list)
# 1 -> 2 -> 3 -> None
print(reverse_list(linked_list))
# 3 -> 2 -> 1 -> None
print(linked_list)
# 1 -> None

CodePudding user response：

This happens because the node instance that is returned is not the node instance that was passed to reverse.

It may help to visualise this. At the moment reverse is called, and is about to start the reversal, we have this state:

         curr
         head                                              prev 
          ↓                                                 ↓ 
        ┌───────────┐    ┌───────────┐    ┌───────────┐
        │ value: 1  │    │ value: 2  │    │ value: 3  │
        │ next: ───────> │ next: ───────> │ next: ───────> None
        └───────────┘    └───────────┘    └───────────┘ 
          ↑
         linked_list (global)

Then when reverse has completed its loop, we have this:

curr     head                              prev
 ↓        ↓                                 ↓
        ┌───────────┐    ┌───────────┐    ┌───────────┐
        │ value: 1  │    │ value: 2  │    │ value: 3  │
None <────── :next  │ <────── :next  │ <─────── :next │
        └───────────┘    └───────────┘    └───────────┘ 
          ↑
         linked_list (global)

reverse then returns the prev reference. It is clear that this referenced node is not the same one as the one that linked_list references.

So when print(reverse_list(linked_list)) is called, the __repr__ method will get the node with value 3 as argument, and will thus be able to print all nodes following the next chain.

However, when print(linked_list) is called, the __repr__ method will get the node with value 1 as argument, and when the loop looks for the next attribute, it will find None -- which stops the printing. When you look at the above visualisation, you can see that if you start with linked_list as reference, the nodes with values 2 and 3 are unreachable. linked_list references the tail of the reversed list.

The "solution" is simple: you must capture the value returned by reverse, and you can re-assign it to the linked_list variable:

linked_list = reverse_list(linked_list)

Once that is executed, you get this visualisation:

        ┌───────────┐    ┌───────────┐    ┌───────────┐
        │ value: 1  │    │ value: 2  │    │ value: 3  │
None <────── :next  │ <────── :next  │ <─────── :next │
        └───────────┘    └───────────┘    └───────────┘ 
                                            ↑
                                           linked_list (global)

So change your main script to:

print(linked_list)
# 1 -> 2 -> 3 -> None
linked_list = reverse_list(linked_list)
print(linked_list)
# 3 -> 2 -> 1 -> None