我正在尝试使用递归实现反向链表:
class node:
def __init__(self, data=None):
self.data=data
self.next_node=None
class linked_list:
def __init__(self):
self.head=node()
def push(self, data):
new_node=node(data)
cur_node=self.head
while(cur_node.next_node!=None):
cur_node=cur_node.next_node
cur_node.next_node=new_node
def display(self):
elems=[]
cur_node=self.head
print('Display:')
# print(cur_node)
# print(cur_node.next_node)
# print(cur_node.data)
while(cur_node.next_node!=None):
cur_node=cur_node.next_node
elems.append(cur_node.data)
print(elems)
def lenth(self):
i=0
cur_node=self.head
while(cur_node.next_node!=None):
last_node=cur_node
cur_node=cur_node.next_node
i+=1
print(i)
def reversell_rec(self, node):
# print("Recursive")
cur_node = node
# print(cur_node)
# print(cur_node.next_node)
# print(cur_node.data)
if (cur_node.next_node == None):
self.head.next_node = cur_node
return
self.reversell_rec(cur_node.next_node)
temp=cur_node.next_node
temp.next_node = node
node.next_node = None
ll=linked_list()
ll.push(1)
ll.push(2)
ll.display()
ll.reversell_rec(ll.head)
ll.display()
我得到输出:
Display: #Display before recursion
[1, 2]
Display: #Display after recursion
[]
我试着用不同的方法打印出来,但不知怎么的self.head.next\节点即使我将最后一个节点分配给self.head.next\节点到最后一个节点。是什么导致了这种变化?你能帮忙吗?你知道吗
编辑:
def reversell_rec(self, node):
# print("Recursive")
cur_node = node
# print(cur_node)
# print(cur_node.next_node)
# print(cur_node.data)
if (cur_node.next_node == None):
self.head.next_node = cur_node
return
self.reversell_rec(cur_node.next_node)
if(cur_node!=self.head):
temp = cur_node.next_node
temp.next_node = cur_node
cur_node.next_node = None '
这看起来是可变的。如果你想这样做的话,基本的想法是通过向后积累来构造一个反向。你知道吗
但老实说,如果你在一个循环中做的话,如果它是可变的,那就容易多了。你知道吗
递归的基本条件是跳过其中一个元素。您正在执行
self.head.next_node=cur_node
,而不是将self.head
本身赋给最后一个元素。你知道吗我对
reversell_rec
函数做了一点修改:由于您使用了“None”头,因此我还必须更改
display
函数:相关问题 更多 >
编程相关推荐