是否可以反转双向循环链表？如果是，那么如何？

Question

我有点困惑，因为我的一位朋友说这不可能。因为它是完全对称的。

我用谷歌搜索了一下，但我还是很困惑

Answer 1

是；只需交换 previous 和 next 指针，以及任何 head 和 tail 指针。你能解释一下你的朋友是如何声称列表是对称的吗？

Answer 2

这并非不可能，它可能需要特别小心地设计算法，但对于大多数（所有）算法而言，您必须迭代和修改数据结构。

您可以简单地交换 head 和 tail，然后遍历您的链表并将 next 和 previous 引用交换为每个个节点。您还需要确保在一次完整迭代后停止这样做。

Python 中的示例算法如下所示：

class CircularDoubleLinkedList:

    # ...

    def reverse(self):
        <b>self.head, self.tail = self.tail, self.head</b>
        start = cur = self.head
        if cur is not None:
            <b>cur.next, cur.previous = cur.previous, cur.next</b>
            cur = cur.previous
        while cur is not None and cur is not start:
            <b>cur.next, cur.previous = cur.previous, cur.next</b>
            cur = cur.previous  # move to the next node

Answer 3

对于列表的每个节点 N，您只需交换 N.next 和 N.prev。在此之后，您将 head 的引用更改为新的 head.next。如果有tail，应该更新为tail.prev.

只是为了更好的可视化：

是否可以反转双向循环链表？如果是，那么如何？

Is it possible to reverse a doubly circular linked list? if Yes, then how?

algorithm

data-structures

doubly-linked-list