我正在使用 Python 解决链表分区问题。目标是将链表分成 2 个部分,第一个部分的值小于 x,第二个部分的值等于或大于 x。
我在分区函数的第一行感到困惑:
current = ll.tail = ll.head
为什么这一行没有永久覆盖 ll.tail
的值?我认为 Python 是一种对象通过引用传递的语言。 ll
、ll.head
和 ll.tail
都是对象,所以我预计这一行会导致 use 丢失存储在ll.tail
.
ll.tail
存储了函数输出所必需的值,它仍然存在于函数的输出中(并且输出是正确的),但我不明白这是怎么回事。
分区.py:
from LinkedList import LinkedList
def partition(ll, x):
current = ll.tail = ll.head
while current:
nextNode = current.next
current.next = None
if current.value < x:
current.next = ll.head
ll.head = current
else:
ll.tail.next = current
ll.tail = current
current = nextNode
# Error check in case all nodes are less than x
if ll.tail.next is not None:
ll.tail.next = None
ll = LinkedList()
ll.generate(10, 0, 99)
print(ll)
partition(ll, ll.head.value)
print(ll)
链表.py:
from random import randint
class LinkedListNode:
def __init__(self, value, nextNode=None, prevNode=None):
self.value = value
self.next = nextNode
self.prev = prevNode
def __str__(self):
return str(self.value)
class LinkedList:
def __init__(self, values=None):
self.head = None
self.tail = None
if values is not None:
self.add_multiple(values)
def __iter__(self):
current = self.head
while current:
yield current
current = current.next
def __str__(self):
values = [str(x) for x in self]
return ' -> '.join(values)
def __len__(self):
result = 0
node = self.head
while node:
result += 1
node = node.next
return result
def add(self, value):
if self.head is None:
self.tail = self.head = LinkedListNode(value)
else:
self.tail.next = LinkedListNode(value)
self.tail = self.tail.next
return self.tail
def add_to_beginning(self, value):
if self.head is None:
self.tail = self.head = LinkedListNode(value)
else:
self.head = LinkedListNode(value, self.head)
return self.head
def add_multiple(self, values):
for v in values:
self.add(v)
def generate(self, n, min_value, max_value):
self.head = self.tail = None
for i in range(n):
self.add(randint(min_value, max_value))
return self
最佳答案
您认为有问题的线路不是您的问题。此代码显示了原因:
def checker(ll):
current = ll.tail = ll.head
print(current)
print(ll.tail)
print(ll.head)
return
ll = LinkedList()
ll.generate(10,0,99)
print(ll)
checker(ll)
print(ll.tail)
print(ll.head)
print("Some other interesting behavior:")
ll.head.value = -1
print(ll.head)
print(ll.tail)
ll.head = -2
print(ll.head)
print(ll.tail)
使用您自己的 LL 代码可以得到:
73 -> 39 -> 14 -> 5 -> 47 -> 29 -> 14 -> 66 -> 70 -> 9
73
73
73
73
73
Some other interesting behavior:
-1
-1
-2
-1
所以你传递的链表在函数内修改时确实会改变。还要注意最后的行为:ll.tail 现在指向 ll.head 指向的位置,而不是 ll.head 本身。这与 C 的指针引用不同。
这意味着您的算法没有按照您的预期进行。特别是我会关注循环何时结束以及它执行的交换顺序(通常这是 LL 事件的大多数错误似乎发生的地方)。
一般的调试技术,如对潜在功能(或预期的错误原因)进行单元测试,是非常重要的编程技能。如果您认为某些东西不起作用(或确实起作用),请对其进行测试。它会缩小您的错误搜索范围,并帮助其他人在您自己无法解决问题的情况下更快地回答您的问题。
关于python - 为什么这个 Python 对象属性没有被永久覆盖?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44992362/