代码之家 › 专栏 › 技术社区 › mattalxndr

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

variable-assignment pass-by-reference linked-list python-3.x python

mattalxndr · 技术社区 · 7 年前

我试图在适当的位置编辑列表以节省空间,因此该方法更改原始列表对象,并且不返回任何内容。也就是说如果 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 ,现在也是周期性的。

下面是一些单元测试失败的可运行代码(请参阅功能):

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

1 回复 | 直到 7 年前

Kalyan Vedala 7 年前

此Stackoverflow 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

倒排列表 , head 仍然指向第一个节点,但它有值 4 head.next 指向包含 3

我的建议是,返回对反向列表的第一个节点的引用。修改过的 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,在阅读您的评论时,主要的问题似乎是如何在不返回值的情况下“原地”反转列表。我能想到的最简单的解决办法是:

制作列表的副本(保存到 copied_list
颠倒
开始从左到右遍历原始列表
开始遍历 复制的清单
复制 val 从 复制的清单

此技术生成列表的另一个副本,因此使用O(n)空间。可能有更好的算法,但我现在想不出。