CareerCup

Your solution is not terribly efficient. How about just using only one pointer. Walk the whole list and find N. Now walk again and report N/3rd node and 2N/3rd node. The O(N) is the same.

Seems like an pretty trivial question. Maybe the interviewer is expecting how will you maintain a linked list such that a 1/3rd and 2/3rd query could be answered as efficiently as possible ?

I second original solution. This problem is a variation of classic "Find the Middle of LL" problem. Original method traverse n + 2n/3 + n/3 = 2n elements in total, whereas your approach traverses n + 2n/3 = 5n/3. But, the former method is likely to have many cache hits, while your approach won't have if the list is too big, say, 10M entries. So the run time would be much faster in original method.

Fastest solution is too obvious. Read the list to an Array, and print n/3rd and 2n/3rd index element. It needs n traverses and O(n) extra memory.

If the interview is not happy with that, give solution based on skip list. O(log N) loop up for k-th position element is achievable on average.

There's definitely not guaranteed to be a big difference in cache performance. I would prefer the two-pass approach because it more easily generalizes to more complicated cases.

Two pass approach is little bit more efficient for it traverses 1 2/3 of the full length of the list, while the one pass approach actually takes two full length traverse (1 + 1/3 + 2/3).

One pass approach is inefficient.. think of large scale.. million/billion list entries.. it gets stumped as it will traverse N+2N/3 times.

Always exercise caution when you write pointer1.next.next ... Cos if pointer1.next == null then next.next will be null pointer exception .. I was corrected by the intervievwer on this .. so always check for null condition ..