CareerCup

How about using BinarySearch? Ar running time of the BinarySearch is o(log n).

Finding the number of elements in the list / finding the mid of the linked list will take o(n) worst case. ~ o(n/2). Hence its o(n) again.

Linklist is a serial access data structure , not random access like array. In order to access any node in the linklist we have to traverse from the start of the link list to that node. In array Accessing any element is a O(1) operation where as in linklist it is O(n).

The (log n) efficiency of the binary search is inversely proportional to the access time of the middle element. In binary search we access the middle element log(n) times, as the access time of linklist is O(n) the time complexity of binary search in linklist becomes O(nlogn).

The best inplace solution would be linear search O(n).

One can try the slow/fast pointer to reduce the complexity to O(n/x + x) where n is number of nodes and x is size of step.

Is it a simple O(n) algo, traversing through the list ? or something special about this question ?

Yes its O(n) except that you can terminate the search once you reach a higher value (if sorted in Ascending order)

is there any way to do it better than 0(n) ?

We may do this in O(n/2) my having 2 pointers corresponding to even and odd elements ..in this way in the worst case also it loop will run for O(n/2) times...