Binary Search in Linked List

[tene]

An interviewer asked me to search nth node in a linked list.
I gave him the logic of linear search, iterating till the nth node.
He wants a faster approach.
If we have 1000 nodes and if we want to search the 999th node , its costlier.

Can some one tell me a wayto achieve this?

[Bazzy]

For which kind of linked list?

[tene]

The normal singly linked list, which we develop using nodes..

[firedraco]

On an arbitrary element, I don't think there is anything faster than linear time (O(n)). I think you would have to switch to a different kind of container to get faster access.

[tene]

Thats what I am also wondering..
I think its not possible to reach an intermediate node, without iterating through the nodes till there.