Gen*_*adi 4 algorithm linked-list time-complexity data-structures
我已经解决了这个问题:
假设您有一个双向链表和一个指向该列表中某个元素的指针.假设你想要在列表中搜索某个值v,你知道它存在于某个地方.除了p之外不使用指针,设计用于查找v的Θ(m)-time算法,其中m是p与包含v的节点之间的距离.不要修改输入列表.
有没有人有任何想法如何解决这个问题？我能想到的唯一方法是破坏性地修改列表.
作为提示:如果向前迈出一步,向后退两步,向前退步四步,退回八步等,会发生什么？找到元素需要多少步骤？
在进行分析时,您可能会发现总结几何序列很有用.如果有帮助,1 + r + r 2 + r 3 + ... + r n-1 =(r n - 1)/(r - 1).
希望这可以帮助!