No idea about directions from Leeds (try multimap or RAC route planner) but there is are car parks directly across the road from the Trinity Street Entrance and I have never had a problem getting a space on one.
Just beware, there is an NCP car park which charges �3.50 but last time we went, a man in a plain yellow reflective jacket (no NCP jacket or anything) was standing at the entrance, trying to tell us it was full and directing us to another car park a bit further up - parking on private land where they were charging �8! My friend insisted he let her on to the NCP (and virtually ran him over to get onto it) and found it was half empty and he had been lying...