In this paper we describe an adaptive softening length formalism for collisionless N-body and self-gravitating Smoothed Particle Hydrodynamics (SPH) calculations which conserves momentum and energy exactly. This means that spatially variable softening lengths can be used in N-body calculations without secular increases in energy. The formalism requires the calculation of a small additional term to the gravitational force related to the gradient of the softening length. The extra term is similar in form to the usual SPH pressure force (although opposite in direction) and is therefore straightforward to implement in any SPH code at almost no extra cost. For N-body codes some additional cost is involved as the formalism requires the computation of the density via a summation over neighbouring particles using the smoothing kernel. The results of numerical tests demonstrate that, for homogeneous mass distributions, the use of adaptive softening lengths gives a softening which is always close to the `optimal' choice of fixed softening parameter, removing the need for fine-tuning. For a heterogeneous mass distribution (as may be found in any large scale N-body simulation) we find that the errors on the least-dense component are lowered by an order of magnitude compared to the use of a fixed softening length tuned to the densest component. For SPH codes our method presents a natural and elegant choice of softening formalism which makes a small improvement to both the force resolution and the total energy conservation at almost zero additional cost.