Given a single linked list, how do we split it into two halves.
For example the list 1->2->3->4 should be divided into 1->2 and 3->4
If the length of the list is odd, add the extra node to first half; so 1->2->3 should be split to 1->2 and 3.
This problem can be efficiently solved using fast pointer, slow pointer mechanism explained in this post.
In this approach, the fast pointer moves two steps at a time where as the slow pointer moves one step at a time. By the time the fast pointer reaches the end of the list, slow pointer will be pointing to the end node of the first half. So we need to iterate the list only once.
Here is the C++ implementation.