从另一个对象的变量设置一个对象的变量时出现奇怪的 Python 行为

Question

我创建了一个函数来反转链表，但是发生了一些奇怪的事情，我一直没弄明白。

我正在尝试就地编辑列表以保存 space，因此该方法更改了原始列表对象并且没有 return 任何内容。这意味着如果 reverse_list 方法是最后几行（为清楚起见变量在此处重命名）：

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

但由于某些原因，original_first_node.next上的节点链看起来与new_first_node.next上的不同，而且现在也是周期性的。

这是一些单元测试失败的可运行代码（请参阅 reverse_list 函数中的注释）：

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()

Answer 1

这个 Whosebug post 包含有关传入参数的有用信息 Python：How do I pass a variable by reference?

您的 reverse_list 函数中的以下两行是问题所在：

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

这是我认为正在发生的事情：

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

在 Marker 1，列表如下所示：

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

            ^                          ^
            |                          |
          head                       prev

在 Marker 2，列表如下所示：

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

            ^                          ^
            |                          |
          head                       prev

因此，在reverse_list的末尾，head仍然指向第一个节点，但它的值为4。而 head.next 指向包含 3 的节点，所以你得到如图所示的循环。

我的建议是您 return 引用反向列表的第一个节点。修改后的 reversed_list 如下所示：

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

你的测试可以修改为：

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))

编辑

@mattalxndr，阅读您的评论后，主要问题似乎是如何在没有 return 值的情况下反转列表 "in place"。我能想到的最简单的解决方案是：

创建列表副本（保存到 copied_list）
反转copied_list
开始从左到右遍历原始列表
开始从右到左遍历copied_list
将 val 从 copied_list 复制到原始列表

此技术制作列表的另一个副本，因此使用 O(n) space。可能存在更好的算法，但我现在想不出任何算法。

从另一个对象的变量设置一个对象的变量时出现奇怪的 Python 行为

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

python

linked-list

pass-by-reference

variable-assignment

python-3.x