Skip to content
Advertisement

Reversing a linked list iteratively with Pythonic variable swapping

I was just practicing some Linked List questions when I came across something I couldn’t explain. So I was wondering if anyone could help me out.

If I have a Linked List with nodes implemented as follows

class Node:
    def __init__(self, val, next):
        self.val = val
        self.next = next

I tried reversing the Linked List initially like so and it came up with an AttributeError: 'NoneType' object has no attribute 'next'

prev = None
curr = head
while curr:
    prev, curr, curr.next = curr, curr.next, prev

And then I modified it to and it worked but I can’t seem to wrap my head around it.

prev = None
curr = head
while curr:
    curr.next, prev, curr = prev, curr, curr.next

I’m aware that Python evaluates the RHS as a tuple and then assigns the values on the LHS from left to right but I can’t seem to understand why both code snippets wouldn’t be the same if this is the case.

Advertisement

Answer

You might want to visualize things the following way:

Your first code is equivalent to:

prev = None
curr = head
while curr:
    tmp = curr, curr.next, prev
    prev = tmp[0]
    curr = tmp[1]
    curr.next = tmp[2]

whereas your second code is equivalent to:

prev = None
curr = head
while curr:
    tmp = prev, curr, curr.next
    curr.next = tmp[0]
    prev = tmp[1]
    curr = tmp[2]

you see the difference is, that in one case you first change curr and then you assign to curr.next, whereas in the other case you first change curr.next and then reassign curr.

python executes nothing in parallel.

It has to chose an order which is left to right for the variables to be assigned to.

User contributions licensed under: CC BY-SA
7 People found this is helpful
Advertisement