递归反转自定义链表时,head.next\u节点突然变为非

2024-03-28 11:25:37 发布

您现在位置:Python中文网/ 问答频道 /正文

我正在尝试使用递归实现反向链表:

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 '   

Tags: selfnonenodedata节点defdisplaytemp
2条回答

这看起来是可变的。如果你想这样做的话,基本的想法是通过向后积累来构造一个反向。你知道吗

def reversell_rec(self):
    def rev_node(n, acc):
        if n is None: return acc
        nxt = n.next_node
        n.next_node = acc
        return rev_node(nxt, n)

    self.head = rev_node(self.head, None)

但老实说,如果你在一个循环中做的话,如果它是可变的,那就容易多了。你知道吗

递归的基本条件是跳过其中一个元素。您正在执行self.head.next_node=cur_node,而不是将self.head本身赋给最后一个元素。你知道吗

我对reversell_rec函数做了一点修改:

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 = cur_node
        return
    self.reversell_rec(cur_node.next_node)
    temp=cur_node.next_node
    temp.next_node = cur_node
    cur_node.next_node = None

由于您使用了“None”头,因此我还必须更改display函数:

def display(self):
    elems=[]
    cur_node=self.head
    print('Display:')
    # print(cur_node)
    # print(cur_node.next_node)
    # print(cur_node.data)
    if self.head.data!=None:
        while(cur_node.next_node!=None):
            elems.append(cur_node.data)
            cur_node=cur_node.next_node
    else:
        cur_node=cur_node.next_node
        while(cur_node!=None):
            elems.append(cur_node.data)
            cur_node=cur_node.next_node
    print(elems)

相关问题 更多 >