You are correct that circle collision is a good first approximation. I suggest you compare the square of the distance between the centers instead of the distance, so you can save a lot of square root computations.
The naive approach would have you check check each circle against each circle, for a total of n² comparisons (where n is the number of circles). And you can bring that number down by not checking against circles you have already checked, for a total of n * (n + 1)/2 comparisons.
However, you only care about the heads (and each snake only has one head). So you would have n * s comparisons (where s is the number of snakes). Which is better than n * (n + 1)/2 given that s ≪ n (read: s is much less than n).
Yet, you are correct again in that you should use some space partitioning structure.
I'll suggest to use a hierarchical space partitioning structure - such a quad-tree - because a large snake could be bundled up in a small space. And with that you would have s * log(n) comparisons.
Alternatively, you could add snakes to the hierarchical space partitioning structure, instead of their individual circles.
You can register the snakes by their middle position. Which is the center of one of the circles, if the number of circles is odd… Or it would be half way between two circles if the number of circles is even.
That way you can query for nearby snakes, and you might be able to prune some snake-snake collision by checking if the distance from center to center of the snakes is greater than the sum of the halves of their lengths. If it is, there is no position those snakes can be that they would be able to touch each other.
So you would only have to worry about collisions between snakes that are close enough. It is worth noting that in the game a snake does not collide with itself.
You would have s * log(s) possible snake-snake collisions. Which is potentially better than s * log(n) considering that s ≪ n. But that depends on how efficient we can make a snake-snake collision check.
For each snake-snake collision check, starting back at the naive approach, you would need p * q comparisons (where p is the number of circles of a snake, and q is the number of circles of the other). For a total of s * log(s) * p * q.
However, again, we only care when the head of a snake runs into the other other snake. I'll refer to these as snake-head collisions. If you need both snake-head collisions checks, that brings us down to p + q comparisons. For a total of s * log(s) * (p + q).
But we don't need both snake-head collisions checks! If the head of a small snake is nearby the body of a large one, it does not mean the head of the large one is nearby the body of the small one.
So, wait, rewind. Do not prune snake-snake collision. Prune snake-head collisions. For these prunes follow the same idea as before: check if the distance from the center of the head to the center of the other snake is greater than half the sum of the size of the head and the length of the snake.
And each snake-head collision check requires l comparisons (where l is the length of the snake). And of these we need at most double as before: 2 * s * log(s). For a total of 2 * s * log(s) * l comparisons. Which is good given that l ≪ n.
I had the idea that a large snake is like two shorter snakes connected head to tail. So you could check if the head could be close enough to collide to each half. And so on, like a binary tree. However, note that the sides of the tree are not mutually exclusive. The head of the snake could be close enough to collide with both halves of the other snake.
Yet, it is a good idea to put the circles of a snake in a convenient structure. For example, if you divide the circles in quadrants, and you find in which quadrant the head is…
Yep, make a quad-tree - or similar hierarchical space partitioning structure - per snake. And use it to find circles of the snake that are nearby the head of the other snake. So you don't have to compare the head with all of them. That should bring the number of comparisons down to log(l) per snake-head collision check. For a total of 2 * s * log(s) * log(l) comparisons.
This total of 2 * s * log(s) * log(l) is better than s * log(n) as long as s ≪ l. That is, if you have few large snakes, this is better. If you have a ton of small snakes, then storing all the circles in a single hierarchical space partitioning structure is better.
I believe the boundary condition is very low. I mean that the snakes will grow soon enough. However, if in doubt, profile to find the boundary conditions. Once you know those conditions, you can even write code that decides which approach to use according to those conditions. You might even decide per snake if it is short enough to store all its circles directly in the hierarchical space partitioning structure.
