Un ejemplo en C.
Verás que solo es moverse por el array y las parejas son el elemento actual y el siguiente. Para evitar que un elemento se cuente dos veces seguidas se hace un salto manual.

#include <stdio.h>
 
int main() {
    char array[] = "AMESDIFPPDKEJSDDDJKPPPP";
 
    // Esto es para cualquier tipo de array unidimensional
    unsigned parejas = 0;
    size_t n_elementos = sizeof(array)/sizeof(array[0]);
    for(size_t i=0; i<n_elementos-1; ++i) { // el -1 es para no salirme del array después
        if(array[i]==array[i+1]) {
            ++i; // Esto hace que un elemento no pertenezca a dos parejas
            ++parejas;
        }
    }
    printf("Hay %d parejas de caracteres", parejas);
}

No domino C++ así que no puedo mostrarte cómo se hace con su sintaxis, pero si con C, por si te sirve de ayuda.

Entiendo que más que una lista es una pila, cada vez que insertas algo lo haces en la cabeza y lo que era la lista original pasa a la cola.

¿Qué error te da el compilador?

---

Vale getline, en el primer argumento le pasas el nombre archivo cuando debes pasar su manejador. De igual forma debes reestructurar la función para que termine con un return. Algo así:

string leer(string nombreArchivo,int linea){
    string lineas;
    ifstream archivo;
    archivo.open(nombreArchivo.c_str(),ios::in);
    int contador = 1;
    if(archivo.fail()==true){ //Fallo al abrir el archivo
        cout<<"No se pudo abrir el archivo..."<<endl;
        cin.ignore(cin.rdbuf()->in_avail()+1);
        exit(0); //Sale del programa
    }
 
    while(getline(archivo,lineas)){
        if(contador == linea)
            break;
        else{
            contador++;
        }
    }
    archivo.close();
    return lineas;
}

¿Podrías pasar todo el código para entender que hace el conjunto?

Tienes dos variables locales con el mismo nombre: el primer argumento de la función y la variable local de ésta.

Te lías con los punteros:
seguro que estaVacia espera un puntero;
aux=*raiz; debería ser aux=raiz;
insertarOrdenada ¿espera un puntero a puntero?

Es un ejercicio bonito.
La cosa es que no se hacen tareas. Debes exponer el código que llevas, indicar dónde te has quedado trabado y por qué.

Tu fallo está en que dado un camino te quedas con el tramo más corto, para todo el camino debes devolver la suma de todos los tramos.

Realloc funciona más o menos de esta forma:
Primero asigna un trozo de memoria del tamaño que le indiques, después copia el contenido de de tu viejo puntero al nuevo, libera el viejo y devuelve el nuevo.

Y cómo el puntero cambia, el que no pases por referencia un puntero (un puntero a puntero) no verás los cambios que se han hecho y además tendrás un puntero suelto porque realloc te lo ha liberado.