通過指針約束有效地搜索雙鏈表的值？

Question

我一直在考慮這個問題要解決：

假設給定了一個雙向鏈表和一個指向該列表的一些元素。我們假設你想在列表中搜索一些你知道存在的值v。使用除p以外的指針，設計一個Θ（m）時間算法來尋找v，其中m是p和包含v的節點之間的距離。不要修改輸入列表。

沒有人有任何想法如何解決這個問題？我能想到的唯一辦法是破壞性地修改列表。

Answer 1

我認爲templatetypedef has the correct answer，但是基於問題的原始語句，我們想到了下面的解決方案，它說明列表不能被「破壞或洗牌」，這可能意味着修改它是可以的，如果你可以再次改變它 - 即使這不是真的，我仍然認爲這是一個有趣的方法。

---

它可以很容易地解決與2個指針，對不對？一個要前進，一個回去，同時移動兩個，直到你找到你想要的價值。

現在，這一切都很好，但我們只允許有1個指針。

如果你考慮一個雙重鏈表，我們知道前一個節點的next指針只是一個指向當前元素的指針，所以，如果我們失去它，我們可以重新設置它。

所以我們可以使用p.prev.next作爲免費存儲（和p.prev.prev.next，給予類似的論點）。

所以，我們只能用一個指針向前發展，並存儲在一個p.prev.next回去，適當地移動它，因爲我們走。

一些Java式的僞代碼忽略結束列表檢查，沒有找到它的簡單（我認爲這已經夠複雜了）：

if p.data == v 
    return v 

p = p.next 
p.prev.next = p.prev.prev 

while not found 
    if p == v || p.prev.next == v 
    p.prev.next = p     // restore p.prev.next 
    return v 
    p = p.next 
    p.prev.next = p.prev.prev.next.prev // set up p.prev.next from p.prev.prev.next 
    p.prev.prev.next = p.prev   // restore p.prev.prev.next 

Answer 2

作爲一個提示：如果你再向前走一步，退兩步，四步向前，八步回來會發生什麼，等等？需要多少步才能找到元素？

在做分析，你會發現它很有用，總結等比數列。如果有幫助，1 + R + R 2 + R + ... + R ^N-1 =（R ^Ñ - 1）/（R - 1）。

希望這會有所幫助！