我最近遇到了一个问题，通过一些阅读，我了解到有一种方法可以在恒定时间内反转双向链表，只需交换头指针和尾指针即可。
现在，考虑问题的一个稍微不同的版本，如果我们只想反转双向链表的子列表(从 x 到 y)，该怎么办？
0->1->2->3->4->5->6->7->8->9 其中 (x = 2, y = 7 )
会成为:
0->1->7->6->5->4->3->2->8->9
最佳答案
你可以，但是你会弄乱链接列表。 基本上，我们向每个节点添加一点，说明此时是否应该颠倒顺序。 接下来，您修改迭代器以异或目前为止看到的所有这些新位。
迭代器现在将根据位的异或选择下一个/上一个或上一个/下一个。
现在您可以在 O(1) 时间内反转链表中的任意间隔，但是您会失去迭代器一致性:任何交换操作都可能使现有迭代器无效。而且代码会非常困惑，所以如果可能的话我会避免它。
要进行实际的翻转，您需要更改(添加空检查以确保不会崩溃)
(first->prev,last->next) = (last->next, first->prev)
last->next->next = last
first->prev->prev = first
last.reverse_here = !last.reverse_here
first->prev.reverse_here = !first->prev.reverse_here
Invalidate_all_existing_iterators()
把它画在纸上，因为它很困惑。
关于algorithm - 反转双向链表的子列表，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/34132185/