反向双重链表的问题

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。转折("b","e")。因此，endptt1 = 'b'， endpt2 = 'e'。然后比较endpt1和current。数据，然后访问endpt2.next。endpt2是单字符字符串。

根本不引用先前的指针。

您唯一尝试更改任何内容的时间是当您命中节点b时。然后，您似乎试图交换b和e的下一个指针(因此b。next是f和e。下一个是 c ,但仅此而已。

在这一点上，我希望你的前向链接给你两个列表:a->b->f和c->d->e->c(一个循环)，并且反向链接保持不变。

拿起铅笔和纸或白板，一次一个陈述地回顾这些变化;这就是我所做的……

---

我从你上一篇文章中恢复了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__可以完成这项工作，但是您使用了列表头指针，就好像它是前向链表上的可迭代对象。

我强烈建议您备份并使用增量编程来处理此问题:编写一个方法或几行，测试它，然后不要继续，直到它像您期望的那样工作。是的，这意味着您正在编写详细的测试……这是一件好事。保持它们，继续运行它们