SignUtil.java

import org.web3j.crypto.Keys;
import org.web3j.crypto.Sign;
import org.web3j.utils.Numeric;

import java.security.SignatureException;

public class SignUtil {

    private static final String GETH_SIGN_PREFIX = "\u0019Ethereum Signed Message:\n32";

    /**
     * This method is expecting the signed message to be a hash of the original message. The length of the message is
     * then hardcoded to 32. Also, this might only work for messages signed by geth, not sure if other clients
     * add the prefix to the signed message.
     * @param signedHash
     * @param originalMessageHashInHex
     * @return
     * @throws SignatureException
     */
    public static String getAddressUsedToSignHashedMessage(String signedHash, String originalMessageHashInHex) throws SignatureException {
        byte[] messageHashBytes = Numeric.hexStringToByteArray(originalMessageHashInHex);
        String r = signedHash.substring(0, 66);
        String s = "0x"+signedHash.substring(66, 130);
        String v = "0x"+signedHash.substring(130, 132);
        System.out.println();
        byte[] msgBytes = new byte[GETH_SIGN_PREFIX.getBytes().length + messageHashBytes.length];
        byte[] prefixBytes = GETH_SIGN_PREFIX.getBytes();
        System.arraycopy(prefixBytes, 0, msgBytes, 0, prefixBytes.length);
        System.arraycopy(messageHashBytes, 0, msgBytes, prefixBytes.length, messageHashBytes.length);
        String pubkey = Sign.signedMessageToKey(msgBytes,
                new Sign.SignatureData(Numeric.hexStringToByteArray(v)[0],
                        Numeric.hexStringToByteArray(r),
                        Numeric.hexStringToByteArray(s)))
                .toString(16);
        System.out.println("");
        System.out.println("Pubkey: " + pubkey);
        String address = Keys.getAddress(pubkey);
        return address;
    }
}

One more cleaned-up gist to hopefully help the next person, with a runnable demo and detailed explanation: https://gist.github.com/djma/386c2dcf91fefc004b14e5044facd3a9

    /**
     * This method is the reverse of the signing process.
     * 
     * @param signedMessageInHex
     *                           The signature in hex format. It is 65 bytes long,
     *                           32 bytes for r, 32 bytes for s, and 1 byte for v.
     *                           May or may not be pre-pended with "0x".
     * @param originalMessage
     *                           The original message that was signed. Not hashed.
     * @return
     *         The address that was used to sign the message.
     * @throws SignatureException
     */
    public static String getAddressUsedToSignHashedMessage(String signedMessageInHex, String originalMessage)
            throws SignatureException {
        if (signedMessageInHex.startsWith("0x")) {
            signedMessageInHex = signedMessageInHex.substring(2);
        }

        // No need to prepend these strings with 0x because
        // Numeric.hexStringToByteArray() accepts both formats
        String r = signedMessageInHex.substring(0, 64);
        String s = signedMessageInHex.substring(64, 128);
        String v = signedMessageInHex.substring(128, 130);

        // Using Sign.signedPrefixedMessageToKey for EIP-712 compliant signatures.
        String pubkey = Sign.signedPrefixedMessageToKey(originalMessage.getBytes(),
                new Sign.SignatureData(
                        Numeric.hexStringToByteArray(v)[0],
                        Numeric.hexStringToByteArray(r),
                        Numeric.hexStringToByteArray(s)))
                .toString(16);

        return Keys.getAddress(pubkey);
    }

 public static String ecRecover(String msg, String sig) {
    byte[] signatureBytes = Numeric.hexStringToByteArray(sig);
    Sign.SignatureData signatureData = sigFromByteArray(signatureBytes);

    try {
        BigInteger recoveredKey = Sign.signedPrefixedMessageToKey(msg.getBytes(), signatureData);
        String address = "0x" + Keys.getAddress(recoveredKey);
        return address.toLowerCase();
    } catch (Exception e) {
        log.error("SignatureException, msg:{}, sig:{}, nonce:{}: ", msg, sig, nonce, e.getMessage());
    }
}

public static Sign.SignatureData sigFromByteArray(byte[] sig) {
    if (sig.length < 64 || sig.length > 65) return null;
    byte  v = sig[64];
    if (v < 27) v += 27;

    byte[] r = Arrays.copyOfRange(sig, 0, 32);
    byte[] s = Arrays.copyOfRange(sig, 32, 64);

    return new Sign.SignatureData(v, r, v);
}