Q:

Algorithm for truck moving around a circle of gas stations

You have a truck moving around a circular track with gas stations spaced out around the circle. Each station has a finite amount of gas. The gas tank on the truck is infinitely big. The distance between the gas stations requires a certain amount of gas to traverse. You can only move in one direction. 
What is the algorithm to use? 
Which gas station do you start at? 
Can you get all the way around and back to the start station?

A:

Yes O(n) is possible. Definitely not TSP.
Let xi be the amount of gas available at station i minus the amount of gas required to go to next station.
A requirement is Σ xi ≥ 0 (enough gas to complete a full circle).
Consider  Si = x1 + x2 + ... + xi
Note that Sn ≥ 0.
Now pick the smallest (or even largest will do, making it easier to write code for) k such that Sk is the least and start at the station next to it.
Now for k < j ≤ n, we have the gas in tank = Sj - Sk ≥ 0.
for 1 ≤ j ≤ k, we have gas in tank = xk+1 + .. + xn + x1 + x2 + .. + xj = Sn - Sk + Sj ≥ 0.
Thus starting at k+1 will ensure there is enough gas accumulated at each station to get to the next station.
// C++ code. gas[i] is the gas at station i, cost[i] is the cost from station i to (i+1)%n
int circ(vector<int> &gas, vector<int> &cost) {
    int min_S=INT_MAX, S=0, position=0;
    for(int i=0;i<gas.size();i++)
    {
        S += gas[i] - cost[i];
        if(S<min_S)
        {
            min_S = S;
            position = (i+1) % gas.size();
        }
    }
    if(S>=0)
        return position;
    else
        return -1;
}

A:

Here's an approach that works in O(n) time and O(1) space (as opposed to O(n) space for Aryabhatta's answer). 
Start at any station, call it station 0, and advance until you run out of gas. If you don't run out of gas, done. Otherwise, if you run out between stations k and k+1, start over again at station k+1. Make a note if you pass 0 again, and if you run out after that it can't be done.
The reason this works is because if you start at station i and run out of gas between stations k and k+1, then you will also run out of gas before station k+1 if you start at any station between i and k.
Here's an algorithm, given an arrays P (petrol) and D (distance):
int position = 0;
int petrol = P[0];
int distance = D[0];

int start = 0;
while (start < n) {
    while (petrol >= distance) {
        petrol += P[++position % N] - distance;
        distance = D[position % N];
        if (position % N == start)
            return start;
    }
    start = position;
    petrol = P[start];
}
return -1;

A:

Let cost be an array of the costs to the next station and gas be an array of how much fuel we can refill
We calculate the difference between gas[i] and cost[i], called diff, where i is the current gas station we are at.
If cost[i] > gas[i] (or diff < 0), it means we need to have at least cost[i] - gas[i] fuel when arriving at station i to make it to the next stop, i + 1. If cost[i] <= gas[i] (diff >= 0), it is a valid starting point because we can start without gas, fill up, and head to the next station. At worst, we will reach the next stop with an empty tank. At best, we will have extra fuel left when we reach i+1 (diff > 0)
We actually don’t have to start from one station, traverse n gas stations successfully to find out whether there is a valid tour! As long as summed fuel >= summed cost, there will be a valid tour. So we just need to do an O(n) pass of the arrays  
More analysis:
Case1: Tank drops below 0
This will only happen at a stop where diff < 0. There might be another starting point after that which collects enough excess fuel after traveling one round to pass this station. However, all those stations which we have passed before will not help, so we do not need to consider them (look at case 2 explanation). 
Case 2: Tank currently >=0, but we encounter another valid starting point
We can safely ignore this because:
A —— B —— C. If B can reach C, and A can reach B, then A can reach C.
Case 3: Tank currently >=0, not a valid starting point
Continue proceeding to the next one
Case 4: Managed to reach the original starting point!
Yay!
def find_starting_station(gas, cost):
    sum_gas = sum_cost = tank = start = 0

    for i in range(0, len(gas)):
        sum_gas += gas[i]
        sum_cost += cost[i]
        tank += gas[i] - cost[i]

        if tank < 0:
            tank = 0
            start = i+1

    if sum_gas < sum_cost: 
        return -1 

    return start

