State design pattern but avoiding singletons

This is getting little bit tricky. I am using state pattern in my application to manage states. I want to have a single instance of each state in my application but I do not want to make each state class as a singleton class. The other approach that is coming to my mind is writing a StateLocator class. StateLocator can be singleton and it can hold instances of all the states. Please guide me on whether StateLocator looks to be a good solution or are there any other solutions where I will still be able to have only one instance of the state and can potentially avoid singletons.

Any help is appreciated. e.g.

public interface TestState {

    public void onTest();  
    public void onApprove()

}

class StateA implements TestState {  
    public void onTest() {  
    }  
    public void onApprove() {  
    }  
}  

class StateB implements TestState {  
    public void onTest() {  
    }  
    public void onApprove() {  
    }  
}   

class StateLocator {  

    private StateA mStateA;   
    private StateB mStateB;  

    StateLocator() {  
        mStateA = new StateA();  
        mStateB = new StateB();  
   }  

   public TestState getState(int stateType) {

      if(stateType == 1) {
          return mStateA;
      } else {
         return mStateB;
      }
  }  
}  

StateLocator, in the way you are using it, is the "Registry" pattern

http://martinfowler.com/eaaCatalog/registry.html

Knowing nothing about your design, this is a good way to avoid singletons. The registry could be a singleton ( doesn't have to be necessarily ).