Efficiently searching a doubly-linked list for a value with a pointer constraint?

Question

I have been given this problem to solve:

Suppose you're given a doubly-linked list and a pointer to some element of that list. Let's suppose that you want to search the list for some value v, which you know exists somewhere. Using no pointers except p, design an Θ(m)-time algorithm for finding v, where m is the distance between p and the node containing v. Do not modify the input list.

Does anyone have any ideas how to solve this? The only way I can think of doing this destructively modifies the list.

Answer 1

As a hint: What happens if you take one step forward, two steps back, four steps forward, eight steps back, etc.? How many total steps will it take to find the element?

When doing the analysis, you might find it useful to sum up a geometric series. If it helps, 1 + r + r² + r³ + ... + r^n-1 = (rⁿ - 1) / (r - 1).

Hope this helps!