algorithm to find middle element of linked list @ O(n/2) order
May 10, 2013 1 Comment
Since every node in a linked list has the reference to its next node, we can achieve this solution by taking two pointers.
For every increment in one pointer, increment the second pointer twice, in this way by the time second pointer reaches the end of the linked list, first pointer should reach the middle element of the linked list.
public void traverse(Node node) {
tmp = node;
while (tmp != null && tmp.next != null) {
node = node.next;
tmp = tmp.next.next;
}
System.out.println("Middle element of the list is: " + node.value);
}
Note: With this logic, in any linked list we can find 1/2th element (with above logic) OR 1/3rd element (by replacing the code ‘tmp = tmp.next.next;’ to tmp = tmp.next.next.next;) OR 1/4th element (by replacing the code ‘tmp = tmp.next.next;’ to tmp = tmp.next.next.next.next;), so on
coding algorithms 
One very similar approach to it will be to use counter approach (though v.same to your approach) as mentioned here:
// Function to get to the middle of the LL
mynode *getTheMiddle(mynode *head)
{
mynode *middle = (mynode *)NULL;
int i;
for(i=1; head!=(mynode *)NULL; head=head->next,i++)
{
if(i==1)
middle=head;
else if ((i%2)==1)
middle=middle->next;
}
return middle;
}