AddressWrapper[] addressList = new AddressWrapper[0];
for(Address key: addresses.keyset()) {
    addressList.add(new AddressWrapper(key, addresses.get(key));
}
addressList.sort();
// addressList[0].address contains the most used address

AddressWrapper[] addressList = new AddressWrapper[0];
for(Address key: addresses.keyset()) {
    addressList.add(new AddressWrapper(key, addresses.get(key)));
}
addressList.sort();
// addressList[0].address contains the most used address

I've edited the changes together and cleaned up the code; this code runs in execute anonymous:

public class AddressWrapper implements Comparable {
    public Address address;
    public Integer counter;
    public AddressWrapper(Address address, Integer counter) {
        this.address = address;
        this.counter = counter;
    }
    public Integer compareTo(Object other) {
        return counter-((AddressWrapper)other).counter;
    }
}

public static void completeaddresses() {
    Account[] acctList = [
        SELECT BillingState, BillingPostalCode, BillingCity, BillingStreet, BillingCountry, BillingAddress, 
            (SELECT MailingAddress, MailingStreet, MailingCity, MailingState, MailingPostalCode, MailingCountry 
             FROM account.contacts WHERE MailingStreet <> NULL OR MailingCity <> NULL OR
                  MailingPostalCode <> NULL OR MailingCountry <> NULL OR MailingState <> NULL)
        FROM Account
        WHERE BillingState <> NULL AND BillingPostalCode <> NULL AND BillingCity <> NULL AND BillingStreet <> NULL];
    
    for (Account acct:acctList) {
        Map<Address, Integer> addresses = new Map<Address, Integer>();
        for (Contact cont:acct.contacts) {
            if (!addresses.containsKey(cont.MailingAddress)) {
                addresses.put(cont.MailingAddress,0);
            }
            Integer currentCount = addresses.get(cont.MailingAddress) + 1;
            addresses.put(cont.MailingAddress, currentCount);
        }
        AddressWrapper[] addressList = new AddressWrapper[0];
        for(Address key: addresses.keyset()) {
            addressList.add(new AddressWrapper(key, addresses.get(key)));
        }
        addressList.sort();
        // addressList[0].address contains the most used address
    }
}

Your best bet is to write a wrapper for this.

public class AddressWrapper implements Comparable {
    public Address address;
    public Integer counter;
    public AddressWrapper(Address address, Integer counter) {
        this.address = address;
        this.counter = counter;
    }
    public Integer compareTo(Object other) {
        return counter-((AddressWrapper)other).counter;
    }
}

Which you would then populate:

AddressWrapper[] addressList = new AddressWrapper[0];
for(Address key: addresses.keyset()) {
    addresses.add(new AddressWrapper(key, addresses.get(key));
}
addressList.sort();
// addressList[0].address contains the most used address

Your best bet is to write a wrapper for this.

public class AddressWrapper implements Comparable {
    public Address address;
    public Integer counter;
    public AddressWrapper(Address address, Integer counter) {
        this.address = address;
        this.counter = counter;
    }
    public Integer compareTo(Object other) {
        return counter-((AddressWrapper)other).counter;
    }
}

Which you would then populate:

AddressWrapper[] addressList = new AddressWrapper[0];
for(Address key: addresses.keyset()) {
    addressList.add(new AddressWrapper(key, addresses.get(key));
}
addressList.sort();
// addressList[0].address contains the most used address