Ideally you want a source of reflection, often the amulet from Sokoban, or SDSM if you can manage it, to handle Medusa. A source of blindness and a Hand Mirror works as well, although almost requires telepathy, or at least Warning, to ensure you reflect the appropriate creature. Hand mirrors are trivially acquired from nymphs, and sources of blindness are often relatively easy to find as well. Make sure to identify potions, or just find a towel or blindfold.
For her level, you will want a source of levitation, or water walking. Boots are fairly reliable, rings can be destroyed by Electric eels, so should be avoided unless you have warning (Orb of Fate) or telepathy. As a Valkyrie, twoweaponing with an artifact (probably Excalibur), you shouldn't have too much trouble destroying anything that manages to grab you, but to be safe I'd recommend a large, disposable stack of a ranged weapon.
Reliable traversal of her level can be difficult to come by, but isn't strictly necessary at this stage. You can dig down with a pickax, trivially acquirable from the mines if you've missed one, or a wand of digging, then go up the stairs from the lower level right into her lair. This method is not recommended if you don't have a reliable way to gain levels again to reach your stash, for example the Orb of Fate and Teleport Control. There is also a fairly good chance that the Statue of Perseus in her lair will contain boots of levitation, although they're often cursed.
Per your comment, going into more detail about passing her level.
You will ideally want either Levitation or Water walking. The most reliable source for these will be Boots, There is often a pair of Boots of Levitation in the statue of Perseus in the Lair Proper, if you follow the dig and return method. Potions are not reliable due to the danger of running out in the middle of the water, and rings are only reliable if you can avoid electric eels.
If you don't happen to have any of these, you can make do with Jumping Boots, if you have them, or a source of ice (Frost wand/horn). You can also make do with a number of scrolls of Earth, two of which you get from Sokoban, so you know the recipe, and more of which can be gotten with a magic marker.
You can also polymorph into a flying/floating/ceiling-dwelling form.
An amulet of magical breathing or an unbreathing or swimming form works as well, if you don't mind your items getting wet. Oilskin sacks or Greased bags can reduce the effects of submerging yourself.
This is assuming you don't just bypass the level entirely on final ascent with a cursed potion of gain level, and on intermediate ascents with your Orb of Fate and Teleport Control from either Ring or Tengu, which is a completely viable method of dealing with Medusa if you lack fully reliable levitation, and either don't want to risk the dangers of potions, or would prefer to save the potions for the Planes.