我正在编写一个程序,使用双向链表构建堆栈。我需要翻转这个栈的顺序,并且要求运行时间为O(1)。例如:
1 -> 2 -> 3 -> 4
变为
4 -> 3 -> 2 -> 1
我能想到的最快的方法需要O(N)的运行时间。但由于需要使用O(1)的运行时间,因此所有循环都不可行,因为它们都不可避免地取决于堆栈中节点的数量。
有人可以推荐一种合理的解决方法吗?
1 -> 2 -> 3 -> 4
变为
4 -> 3 -> 2 -> 1
我能想到的最快的方法需要O(N)的运行时间。但由于需要使用O(1)的运行时间,因此所有循环都不可行,因为它们都不可避免地取决于堆栈中节点的数量。
有人可以推荐一种合理的解决方法吗?
->prev
和->next
成员,而是使用->link[2]
,并将其作为->link[direction]
和->link[1-direction]
访问。 - R.. GitHub STOP HELPING ICEuintptr_t
来实现。当遍历列表时,如果前一个节点是P
,当前节点是C
,则下一个节点是(struct ListItem *) ((uintptr_t) P ^ C->RecordedXOR)
,无论您在哪个方向上遍历列表。因此,通过交换头和尾记录,该实现具有O(1)翻转时间。不需要方向标志,并且不需要调整节点指针的索引。 - Eric Postpischil