Skip to main content
 首页 » 编程设计

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

2024年12月31日9jiqing9006

我创建了一个函数来反转链表,但发生了一些奇怪的事情,我一直无法弄清楚。

我正在尝试就地编辑列表以节省空间,因此该方法更改了原始列表对象并且不返回任何内容。这意味着如果 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() 

请您参考如下方法:

这篇 Stackoverflow 帖子包含有关在 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 

在标记 1 处,列表如下所示:

None  <---  1  <---  2  <---  3  <---  4 
 
            ^                          ^ 
            |                          | 
          head                       prev 

在标记 2 处,列表如下所示:

        ---------------------- 
       |                      | 
       |                      | 
       |                      v 
       ---  4  <---  2  <---  3  <---  4 
 
            ^                          ^ 
            |                          | 
          head                       prev 

因此,在reverse_list 的末尾,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)
  • 反转copied_list
  • 开始从左到右遍历原始列表
  • 开始从右到左遍历copied_list
  • 将 val 从 copied_list 复制到原始列表

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