snippetMajor
How to find middle element of linked list in one pass?
Viewed 0 times
howpassoneelementfindlistlinkedmiddle
Problem
One of the most popular question from data structures and algorithm, mostly asked on telephonic interview.
Solution
By cheating, and doing two passes at the same time, in parallel. But I do not know whether the recruiters will like this.
Can be done on a single linked list, with a nice trick. Two pointers travel over the list, one with double speed. When the fast one reaches the end, the other one is half-way.
Can be done on a single linked list, with a nice trick. Two pointers travel over the list, one with double speed. When the fast one reaches the end, the other one is half-way.
Context
StackExchange Computer Science Q#56219, answer score: 24
Revisions (0)
No revisions yet.