Finding the middle element of a linked list in Java.
Here is my take on this common problem, all in Java.
1. Knowing the Size
Goes without saying, if we know the size of the list when adding new elements we will always be able to find the middle. Below is an example using Java implementation of a linked list.
Now we are just traversing the list until we reach the middle element.
2. Not knowing the size
In this situation things can get a bit trickier. But not to worry, the solution may not be as far fetched as you think.
First thing is first, we need to create a class to represent a node of the list, which stores string values.
Also, we'll use this helper method in our test cases to create a singly linked list using only our nodes:
Okay great, now the first thing to do is find the size of the list and then we iterate until we find the middle element.
Upon closer examination the above code iterates through the list twice. Therefore it is probably not the best way to solve this.
Iterating only once
Now let us find the middle element with only one iteration. To do this we need two pointers to iterate through the list at the same time. One of which will advance two nodes in each iteration and the other will advance one. So when the faster pointer reaches the end of the list the slower one will be in the middle. Magic!
Finally lets test this using a simple unit test.
And that is that for this problem. Not easy but not impossible, heck I may have even messed up!