In a gravity-free space, one does not walk. You can see, for example, astronauts at the International Space Station doing their thing; it's a lot of "pushing off of walls" etc. to get to where you want to go. You still need energy to push off of walls and to stop, but during the middle you're pretty much flying without resistance -- wind resistance at low speeds is not very much.
Another tool to help in thinking about issues related to walking is a bicycle on a good road. We have a lot of clumsy intuitions about motion which come from the fact that walking is this very clumsy action of maintaining constant balance while sequentially falling over and over again onto your other foot, so we conflate energies to contract muscles with forces with stresses with damage/pain/sensation in complicated ways.
A lot of this can be mitigated by understanding a bicycle on a good road, you have to pedal hard to get up to speed, then at-speed you can just "coast", then you have to expend a lot of energy into the brakes in order to slow down.
You can actually "unpedal" this on some bikes which have a "fixed gear" setup but they are less popular. Basically in fixed gear bikes you do not "coast" in the same way: your legs are always moving forward in a circle as long as you are moving forward. But when you "coast" the pedals just kind of "drag your feet along for the ride" and when you accelerate you push in the way that the pedals are going and when you decelerate you have to "fight" the pedals by pushing the reverse way.
Anyway, the point is that the energy cost of walking is not part of this "we accelerate and decelerate our legs" issue, it's part of the "we decelerate our legs by crashing them into the ground" issue that does not provide us a good way to recoup that energy. This is also why humans can run 20-25 km/hr with jumping stilts on, even though if you ever see people running with jumping stilts, you will think "you were not evolved to run that way..."