3 ms·
The "one pass" solution to find the middle of a linked list visits each element twice (or more precisely, it visits half of the elements twice). It is hardly on
by gpderetta 8y ago
The "one pass" solution to find the middle of a linked list visits each element twice (or more precisely, it visits half of the elements twice). It is hardly one pass.
- zamalek 8y agoThis often trips up people who don't know how big O works (loops are not directly correlated to N), or why it works that way (in general a constant before N is negligible, the curve is more interesting). This single pass approach introduces a conditional branch inside a loop, which I've found to be generally slower on x86 - because I've made that mistake and years later found a huge performance benefit by using the "dumb" (multiple loop) approach.
- tralarpa 8y ago> This often trips up people who don't know how big O works They didn't ask for an algorithm with linear complexity. They explicitly asked for a solution "in one pass". That's highly misleading. Edit (after the reply by zamalek): And you are perfectly right about the performance: it's probably slower than just doing two passes (one to find the length, the second to find the middle).
- zamalek 8y agoAs the root comment points out, both solutions (the second being two loops) are 1.5 passes.
- thaumasiotes 8y agoProposal: Convert the linked list to an indexed structure with dynamic capacity like a vector or a hash table. This is easy to do in one pass. ("Visit the node; add it to the hash table. Visit the next node...") Once you're done, access the middle element. You've reduced the number of passes from 1.5 to 1, and all it took was duplicating the entire input.
- sethammons 8y agoWhich could be ok depending on memory constraints
- thaumasiotes 8y agoWell, it's ok based on this statement of the problem. It's never going to make sense as an approach in reality, because the work you need to do constructing the second data structure is considerably more than the work you'd need to do to make the extra half pass through the linked list. You're losing on space and time by doing it this way.