There is a circular track.There are n gas stations of capacity ci. To go from one station to the next station it takes certain amount of gas gi.

There is a circular track.There are n gas stations of capacity ci. To go from one station to the next station it takes certain amount of gas gi.
For any station the gas available may not be enough to get to the next station.
Write a linear time algorithm to find the correct station in which we must start in order to complete one round around the track.

Take a linked list where each node ni is ci-gi. Two node’s pointers p1 and p2, int sum is 0
Choose a start point randomly, which pointed by p1 and p2.
Calculate sum=sum+ni, if the sum is positive, forward p1 by 1, ni=p1->val; else backward p2, ni=p2->val;
Repeat above until p1 and p2 encounter. If sum is positive, there is a path to go through the list.
nice solution!!!