Efficient Find and Replace

[Murali]

Given: L = list of integers. X and Y are integers.
Problem: find every occurence of X and replace with Y

Solution1:
def check(s):
     if s==X:
        return Y
     else return s

newL = [ check(s) for s in L]

Now I dont want to create another list but just modify it in place.

SolutionA:

for x in range(len(L)):
    if L[x] == X:
       L[x:x] = Y

SolutionB:

p = L.index(X)
while p >= 0:
   L[p:p] = Y
   p = L.index(X)

Problem with both solutions is the efficiency. Both methods require
time O(N^2) in the worst case, where N is the length of the list.
Because L.index() and L[x:x] both take O(N) time in the worst case. But
clearly one should be able to do it in time O(N). Atleast there is a C
solution which does it in O(N) time.

p = head(L)
while (p) {
  if (p->data == X) p->data = Y;
}

Is there a python equivalent of this? using iterators or something
which will allow me efficient serial access to the list elements.

- Murali