Weird Python behavior when setting an object's variable from another object's variable

Question

I created a function that will reverse a Linked List, but there is something weird going on, and I haven't been able to figure it out.

I am trying to edit the list in place to save space, so the method changes the original list object and doesn't return anything. Which means the last lines if the reverse_list method are (variables renamed here for clarity):

original_first_node.val = new_first_node.val
original_first_node.next = new_first_node.next

But for some reason, the node chain on original_first_node.next looks different than that of new_first_node.next, and it's also cyclical now.

Here is some runnable code with a failing unit test (see the comments in the reverse_list function):

import unittest


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


def create_list(list):
    if not list:
        return None
    sentinel = Node(None)
    current = sentinel
    for item in list:
        current.next = Node(item)
        current = current.next
    return sentinel.next


def convert_list(head):
    ret = []
    if head:
        current = head
        while current:
            ret.append(current.val)
            current = current.next
    return ret


def is_list_cyclic(head):
    if not head:
        return False
    tortoise = hare = head
    while hare.next and hare.next.next:
        tortoise = tortoise.next
        hare = hare.next.next
        if tortoise == hare:
            return True
    return False


def reverse_list(head):
    if not head or not head.next:
        return

    current = head
    prev = None
    while current:
        static_next = current.next
        current.next = prev
        prev = current
        current = static_next

    # At this point, prev.next looks great

    head.val = prev.val
    head.next = prev.next

    # head.next is cyclical now for some reason ??


class TestSuite(unittest.TestCase):

    def test_reverse_list(self):
        head = create_list([1, 2, 3, 4])

        reverse_list(head)

        self.assertFalse(is_list_cyclic(head))
        self.assertEqual([4, 3, 2, 1], convert_list(head))


if __name__ == "__main__":
    unittest.main()

Kalyan Vedala · Accepted Answer · 2018-08-17T19:48:29.360

1

This Stackoverflow post contains good information about argument passing in Python: How do I pass a variable by reference?

The following two lines in your reverse_list function are the problem:

head.val = prev.val
head.next = prev.next

Here's what I think is happening:

# Marker 1
head.val = prev.val
head.next = prev.next
# Marker 2

At Marker 1, the list looks like this:

None  <---  1  <---  2  <---  3  <---  4

            ^                          ^
            |                          |
          head                       prev

At Marker 2, the list looks like this:

        ----------------------
       |                      |
       |                      |
       |                      v
       ---  4  <---  2  <---  3  <---  4

            ^                          ^
            |                          |
          head                       prev

Thus, at the end of reverse_list, head still points to the first node, but it has value 4. And head.next points to node that contains 3, so you get the loop as shown in diagram.

My suggestion is that you return a reference to first node of the reversed list. The modified reversed_list would look as follows:

def reverse_list(head):
    if not head or not head.next:
        return

    current = head
    prev = None
    while current:
        static_next = current.next
        current.next = prev
        prev = current
        current = static_next

    return prev

And your test can be modified to:

class TestSuite(unittest.TestCase):

    def test_reverse_list(self):
        head = create_list([1, 2, 3, 4])

        rev = reverse_list(head)

        self.assertFalse(is_list_cyclic(rev))
        self.assertEqual([4, 3, 2, 1], convert_list(rev))

Edit

@mattalxndr, on reading your comments, the main question seems to be how to reverse the list "in place" without returning a value. The simplest solution I can think of is:

make of the copy of the list (save into copied_list)
reverse copied_list
start traversing original list of left to right
start traversing copied_list from right to left
copy val from copied_list to original list

This technique makes another copy of the list, so uses O(n) space. Better algorithms may exist, but I am not able to think of any at this time.

edited Aug 17 '18 at 19:48

answered Aug 16 '18 at 15:00

Kalyan Vedala

1,049
2
17
33

Am I correct in understanding that doing it this way bypasses the original intent of editing the list in-place? – Marcel Wilson Aug 16 '18 at 15:09
The list is still being edited in place. There are no new nodes being created in `reverse_list`, so the original nodes are unchanged, except their `next` variables are being updated to point to different `Node` instances within the list. – Kalyan Vedala Aug 16 '18 at 15:12
It could be that I have the wrong idea about 'in place'; `reverse_list` is returning a new object. This is evidenced by the fact that in order to test the reversal we had to look at `rev` rather than `head`, no? – Marcel Wilson Aug 16 '18 at 15:26
Due to python's pass-by-value, any modifications made to `head` itself within `reverse_list` would not modify what `head` is referring to in `test_reverse_list`. For example, we could add the statement `head = "some_value"` in `reverse_list` and `head` in `test_reverse_list` would still refer to first node of the list. In my understanding, 'in place' means we do not create same number of new nodes as the number of nodes in the original list - to use big-o notation, the `reverse_list` function has to use O(1) additional memory. – Kalyan Vedala Aug 16 '18 at 15:43
I was returning it at some point, but the function was making changes to the node object chain which were being carried back into outer scope. Instead of cleaning it up within the method, I thought it was cleaner to just not return anything and just alter the input, like `Collections.sort(al)` in Java. Yes, I want to stick with O(n) mem, O(1) space. – mattalxndr Aug 16 '18 at 18:11
@rcode74 You said "# At this point in function, `prev` points to the node containing value 4. And `head` is still pointing to node containing 1." This is true, but you didn't address the problem, unless I'm missing something. If you run it through a debugger, you can see that after that assignment, `prev.next` looks different than `head.next`. – mattalxndr Aug 16 '18 at 18:14
@mattalxndr, I have updated my answer to show the effect of the two assignment statements at the end of `reverse_list`. – Kalyan Vedala Aug 16 '18 at 18:35
@mattalxndr, added another edit to the answer with suggested solution. – Kalyan Vedala Aug 16 '18 at 19:20
Makes total sense. Thank you for your solution. – mattalxndr Aug 17 '18 at 08:01
If I return the object, I should not be leaving the input object such a mess. Any idea how I can actually pass the input node by value? – mattalxndr Aug 17 '18 at 08:06
It is not possible to pass collections by value. Although python still passes the "address" of first node by value, the actuals contents of the list are directly accessible within `reversed_list` method. That's the reason I suggested making a copy in the algorithm at end of the answer. – Kalyan Vedala Aug 17 '18 at 19:55

Weird Python behavior when setting an object's variable from another object's variable

1 Answers1