Binary Search in Linked List
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?
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?
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.
Thats what I am also wondering..
I think its not possible to reach an intermediate node, without iterating through the nodes till there.
I think its not possible to reach an intermediate node, without iterating through the nodes till there.
Topic archived. No new replies allowed.