CODEWITHSUNDEEP
python-3.xlinked-list
SDG
SDG

Reputation: 2342

Reversing a LinkedList in with multiple assignment

I have this code right down here:

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if head == None:
            return

        pre, node = None, head
        while node:
            pre, node.next, node = node, pre, node.next

        return pre

I am trying to vizualize how this works. If it starts on a list, the pre becomes the head, since node was assigned to head. then node.next is assigned to pre, so it points to itself? Finally, node becomes node.next, which is itself? am I missing something here?

Upvotes: 1

Views: 718

Answers (3)

Han Qi
Han Qi

Reputation: 503

Here is a related question that links to docs on evaluation order: Tuple unpacking order changes values assigned

From https://docs.python.org/3/reference/expressions.html#evaluation-order, the example expr3, expr4 = expr1, expr2 shows evaluation order through the suffix number. It shows that the right side of assignment is evaluated first, from left to right, then the left side of assignment is evaluated, also from left to right.

For mutable objects like in this question, it gets more confusing without knowing the evaluation order.

To prove that it is indeed left-to-right on the left-hand-side, you can imagine what happens when pre, node.next, node = node, pre, node.next is assigned from right-to-left, meaning:

  1. node = node.next
  2. node.next = pre
  3. pre = node

This wouldn't be reversing the Linked List at all.

Other ways to write this reversal:

Sometimes you can see others express this pattern as pre, pre.next, node = node, pre, node.next (Notice the 2nd element on LHS changed from node.next to pre.next. This still works because after the first evaluation of pre = node, pre and node are referring to the same node. However, it introduces an extra dependency on the first evaluation of pre = node, which adds unnecessary cognitive load on the reader.

If we remained at pre, node.next, node = node, pre, node.next, then even swapping the first two variables (do it on both left and right of assignment) works:

node.next, pre, node = pre, node, node.next. This is also my most preferred form since the right-hand-side naturally follows a previous,current,next order of the linked list.

Generally, we should place the dependent objects on the left of independent objects when ordering a tuple of variables on the left-hand-side. Any ordering with node = node.next before node.next = pre should break the implementation. (One example already shown in the thought experiment above on right-to-left evaluation order.)

Upvotes: 1

Blckknght
Blckknght

Reputation: 104712

Multiple assignment isn't the same as several assignments one after the other. The difference is that the values on the right hand side of the statement all get evaluated before anything get rebound. The values on the right hand side are in fact packed up in a tuple, then unpacked into the names on the left hand side.

That's important in this situation as it means that node.next on the right hand side gets its value saved, so that when you rebind it to something else (pre), the old value is still available to become the new node value after the assignment.

You may want to play around with some simpler assignments, like the classic swap operation:

x = 1
y = 2

x, y = y, x  # swap x and y's values

print(x, y)  # prints "2 1"

_tup = y, x   # this is how it works, first pack the RHS values into a tuple
x, y = _tup   # then unpack the values into the names on the LHS

print(x, y)  # prints "1 2" as we've swapped back

Upvotes: 2

ComplicatedPhenomenon
ComplicatedPhenomenon

Reputation: 4189

The main idea is to convert the original head node becomes the last node of the new linked list and convert the original last one become the new head node and convert the link direction between nodes.

suppose the original linked list consists 2 nodes.

first, pre = None, the node = head, then node.next = pre that means the original head node becomes the last node of the new linked list. node = node.next that means to convert the link direction between nodes. node.next = pre means to convert the original last one becomes the new head.

while repeatedly execute the above process

Upvotes: 1

Related Questions