反转双向链表的问题

Question

我必须反转两个节点之间的双向链表 (DLL)。我已经用单链表（SLL）完成了这个，但我发现用 DLL 做起来更难？这可能是必须在两个特定节点之间进行。这是我的 DLLNode 和 DLL 的代码。当我测试这段代码时，它似乎对我的 DLL 没有任何作用。关于我做错了什么的任何提示？？

编辑：所以我正在输入链表 'a'、'b'、'c'、'd'、'e'、'f'并调用 twist('b','e'): 这应该导致链表 'a' 'b' 'e' 'd' 'c' 'f'

class DoublyLinkedListNode:
def __init__(self, item, prevnode = None, nextnode = None):
    self._data = item
    self.setnext(nextnode)
    self.setprev(prevnode)

def data(self):
    return self._data

def next(self):
    return self._next

def prev(self):
    return self._prev

def setprev(self, prevnode):
    self._prev = prevnode

def setnext(self, nextnode):
    self._next = nextnode

class DoublyLinkedList:
def __init__(self):
    self._head = None
    self._tail = None
    self._length = 0

def _newnode(self, item, nextnode = None, prevnode = None):
    return DoublyLinkedListNode(item, nextnode, prevnode)

def addfirst(self, item):
    if self.isempty():
        return self._addtoempty(item)
    node = self._newnode(item, None, self._head)
    self._head.setprev(node)
    self._head = node
    self._length += 1

def addlast(self, item):
    if self.isempty():
        return self._addtoempty(item)
    node = self._newnode(item, self._tail, None)
    self._tail.setnext(node)
    self._tail = node
    self._length += 1

def _addtoempty(self, item):
    node = self._newnode(item, None, None)
    self._head = self._tail = node
    self._length = 1

def removefirst(self):
    if len(self) <= 1:
        return self._removelastitem()
    data = self._head.data()
    self._head = self._head.next()
    self._head.setprev(None)
    self._length -= 1
    return data

def removelast(self):
    if len(self) <= 1:
        return self._removelastitem()
    data = self._tail.data()
    self._tail = self._tail.prev()
    self._tail.setnext(None)
    self._length -= 1
    return data

def _removelastitem(self):
    if self.isempty():
        return None # Should probably raise an error.
    data = self._head.data()
    self._head = self._tail = None
    self._length = 0
    return data

def twist(self, endpt1, endpt2):
    current = self._head
    while current != None:
        if current.data() == endpt1:
            current.next().setnext(endpt2.next())
            endpt2.setnext(current.next())
            current.setnext(endpt2)
        else:
            current = current.next()

def isempty(self):
    return len(self) == 0

def _nodes(self):
    node = self._head
    while node is not None:
        yield node
        node = node.next()

def __iter__(self):
    for node in self._nodes():
        yield node.data()

def __len__(self):
    return self._length

def __str__(self):
    items = [str(data) for data in self]
    return ", ".join(items)

这是我的测试运行:

    def testtwist1(self):
        n = [0,1,2,3,4,5]
        L = DoublyLinkedList()
        for i in n:
            L.addlast(i)
        L.twist(2,5)
        print(L)   # returns the list 0,1,2,3,4,5

Answer 1

我完全看不出这是如何执行的。您显然已经设置了一个 DLL，然后调用了 DLL.twist('b', 'e')。因此，endpt1 = 'b' 和 endpt2 = 'e'。然后您将 endpt1 与 current.data 进行比较，但随后您访问 endpt2.next。 endpt2 为单字符字符串.

您根本没有引用 prev 指针。

你唯一一次试图改变任何东西是当你点击节点 b 时。然后你似乎试图交换 b 和 e 的 next 指针（所以 b.next是f，e.next是c，仅此而已。

在这一点上，我希望你的前向链接给你两个列表：a->b->f 和 c->d->e->c（一个循环），并且后向链接没有变化.

拿起铅笔和纸或一块白板，逐步了解这些更改，一次一个陈述；这就是我所做的...

我从您之前的 post 中恢复了 twist，修复了缩进，并且运行。正如我在上面解释的那样，这个错误在执行中：

Traceback (most recent call last):
  File "so.py", line 113, in <module>
    L.twist(2,5)
  File "so.py", line 102, in twist
    current.next().setnext(endpt2.next())
AttributeError: 'int' object has no attribute 'next'

没有2.next()这样的东西。我不认为你真的得到了你的 print 声明。此外，print(L) 不会按顺序打印节点值；您没有为 DLL 对象包含 __repr__ 方法。 __str__ 可以完成这项工作，但是您使用列表头指针就好像它是前向链表上的可迭代对象一样。

我强烈建议您备份并通过增量编程来解决这个问题：编写一个方法或几行代码，测试它，直到它按预期工作为止不要继续。是的，这意味着您正在编写详细的测试……这是一件好事。保留它们，并保留运行它们。

反转双向链表的问题

Problems Reversing a Doubly Linked List

python

linked-list

doubly-linked-list