我是数据结构的新手,我试图在Python中迭代地反转链表。下面是代码。
class Node:
def __init__(self, initval=None,next_val=None):
self.value = initval
self.next = next_val
def isempty(self):
return self.value == None
def append(self, val):
if self.isempty():
self.value=val
elif self.next==None:
self.next=Node(val)
else:
self.next.append(val)
return
def insert(self, val):
if self.isempty():
self.value = val
return
newnode = Node(val)
self.value, newnode.value = newnode.value, self.value
self.next, newnode.next = newnode, self.next
return
def delete(self, val):
if self.isempty():
return
if self.value == val:
if self.next ==None:
self.value=None
else:
self.value=self.next.value
self.next=self.next.next
return
else:
if self.next !=None:
self.next.delete(val)
if self.next.value==None:
self.next=None
return
def reverse(self):
prev = None
current = self
while current:
next=current.next
current.next=prev
prev=current
current=next
#print(prev)
return prev
## def __iter__(self):
## node = self
## while node !=None:
## yield node.value
## node=node.next
def __str__(self):
llist=[]
if self.value==None:
return str(llist)
tmp =self
llist.append(tmp.value)
while tmp.next !=None:
tmp = tmp.next
llist.append(tmp.value)
return str(llist)
def main():
l=Node()
for i in [2,7,6,1,4,8,9]:
l.append(i)
print(l,id(l))
print(l.reverse())
print(l,id(l))
if __name__ == "__main__": main()
目前,该程序仅返回反向列表的第一个元素。这是输出。
[2, 7, 6, 1, 4, 8, 9] 47566384
[9, 8, 4, 1, 6, 7, 2]
[2] 47566384
我期待的是:
[2, 7, 6, 1, 4, 8, 9] 47566384
[9, 8, 4, 1, 6, 7, 2]
[9, 8, 4, 1, 6, 7, 2] 47566384
我尝试过的,在 while 循环之外reverse
函数的末尾分配self.value = prev
。然后我在列表中获取一个节点对象,如下所示:
[2, 7, 6, 1, 4, 8, 9] 53661168
None
[<__main__.Node object at 0x03597F10>] 53661168
如何正确显示此节点对象?谢谢。
您正在尝试就地反转链表。
在您的代码中,l
最初是值为 2 的节点。您已成功反转列表。
但是在你调用l.reverse()
之后,l
仍然引用值为 2 的节点。
你不能l
从它自己的方法中引用其他东西。
在方法中用另一个相同类型的对象替换 self 对象是否安全?
事实上,甚至做这样的事情:
def reverse(self):
prev = None
current = self
while current:
next=current.next
current.next=prev
prev=current
current=next
self.val = prev.val
self.next = prev.next
#print(prev)
return prev
不起作用,因为现在您在列表中创建了一个循环 7->9,因为 7 最初指向 self 出于同样的原因,self.__dict__.update(prev.__dict__)
不起作用。
简单地分配self = prev
也是行不通的,因为self
只是本地的。
所以你最好的选择是简单地将 l 分配给 l.reverse()
l = l.reverse()
,l
现在实际上是反向列表的第一个节点。