在 Python 中迭代反转链表后无法分配头

Question

我是数据结构的新手，我试图在 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

如何正确显示这个节点对象？谢谢。

Answer 1

您正在尝试就地反转链表。

在您的代码中 l 最初是值为 2 的节点。您已成功反转列表。

但是调用l.reverse()后，l仍然引用值为2的节点。

你不能让 l 从它自己的方法中引用其他东西。

Is it safe to replace a self object by another object of the same type in a method?

事实上，甚至做这样的事情：

    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 现在实际上是反向列表的第一个节点。

在 Python 中迭代反转链表后无法分配头

Not able to assign head after reversing a linked list iteratively in Python

python

reverse

linked-list

data-structures