I have the following problem shown here:
I am not sure why this answer is correct, or even how to visualize this function's execution. How is the multiple assignment expression shown within the while loop evaluated?
Add a comment
|
2 Answers
Multiple assignment is like single assignment, but all at once - you can provide a tuple of values, and assign a same-length tuple of values, all at once:
a, b, c = 1, 2, 3
a == 1 # True
b == 2 # True
c == 3 # True
So, here's what the function is doing:
def reverse(self):
p, q = self.head, self.head.next # initialize p and q as first two elements of queue
while q: # iterate until q is None (that is, until we reach the end of the list)
# This indicates that we will need to have a way for q to advance
# towards the end of the list. Presumably we'll be setting q as
# something that will eventually be None.
# We know that the `next` of the last element in the list will be
# None, so that's a good starting point.
_____________________ # blank line to fill in
self.head, self.tail = self.tail, self.head # swap head and tail of list with each other
self.tail.next = None # set the next element of the tail to None, as it should be.
So, then, what goes in the blank? Well, we can figure out what each individual variable is going to need to change to. The approach that we'll be taking is to change the direction of every element we encounter - instead of .next pointing to the next element, we'll make it point to the previous element. Thus, we would want
q.next = p
since q is the second element in the list, and p is the element that comes before it. Then, we just want to advance p and q to the next two elements in the list:
p = q
q = q.next
Normally, if we were doing these in separate statements, we would need a temporary variable to store the value of q.next - but multiple assignment lets us bypass that:
q.next, p, q = p, q, q.next
At the end of the process, having reversed all the links between elements, we just reverse the head and tail. And set self.tail.next to None, as self.tail is the element that used to be self.head, and we skipped it initially.
Comments
Once you visualize the singly-linked list on a paper in form of a, well, list, you'll notice that on every iteration all it does is revert the connection:
initial setup:
(1) -> (2) -> (3) -> (4) -> (5) -> nil
p q
step 1:
(1) <- (2) -> (3) -> (4) -> (5) -> nil
p q
step 2:
(1) <- (2) <- (3) -> (4) -> (5) -> nil
p q
step 3:
(1) <- (2) <- (3) <- (4) -> (5) -> nil
p q
step 4:
(1) <- (2) <- (3) <- (4) <- (5) nil
p q
Here,
q.next = pmeans "reverse the connection";p, q = q, q.nextmeans "advance one node forward".
