13 - Ejercicios prácticos sugeridos

Pon en práctica lo aprendido

Estos ejercicios amplían los temas anteriores y ayudan a consolidar la manipulación de listas enlazadas. Cada punto incluye una sugerencia de implementación en C.

13.1 Contar nodos

size_t lista_contar(const Lista *lista) {
  size_t total = 0;
  const Nodo *reco = lista->cabeza;
  while (reco) {
    ++total;
    reco = reco->sig;
  }
  return total;
}

13.2 Invertir la lista

void lista_invertir(Lista *lista) {
  Nodo *prev = NULL;
  Nodo *curr = lista->cabeza;
  while (curr) {
    Nodo *sig = curr->sig;
    curr->sig = prev;
    prev = curr;
    curr = sig;
  }
  lista->cabeza = prev;
}

13.3 Ordenar la lista

Una estrategia simple es usar ordenamiento por inserción, aunque se pueden aplicar algoritmos más eficientes (merge sort).

void lista_ordenar(Lista *lista) {
  if (!lista->cabeza || !lista->cabeza->sig) return;
  Nodo *ordenada = NULL;
  while (lista->cabeza) {
    Nodo *curr = lista->cabeza;
    lista->cabeza = curr->sig;
    if (!ordenada || curr->valor < ordenada->valor) {
      curr->sig = ordenada;
      ordenada = curr;
    } else {
      Nodo *reco = ordenada;
      while (reco->sig && reco->sig->valor < curr->valor) {
        reco = reco->sig;
      }
      curr->sig = reco->sig;
      reco->sig = curr;
    }
  }
  lista->cabeza = ordenada;
}

13.4 Eliminar duplicados

void lista_eliminar_duplicados(Lista *lista) {
  for (Nodo *curr = lista->cabeza; curr; curr = curr->sig) {
    Nodo *prev = curr;
    Nodo *reco = curr->sig;
    while (reco) {
      if (reco->valor == curr->valor) {
        prev->sig = reco->sig;
        free(reco);
        reco = prev->sig;
      } else {
        prev = reco;
        reco = reco->sig;
      }
    }
  }
}

13.5 Fusionar dos listas

Lista lista_fusionar(const Lista *a, const Lista *b) {
  Lista resultado = {0};
  const Nodo *recoA = a->cabeza;
  const Nodo *recoB = b->cabeza;
  while (recoA || recoB) {
    if (recoB == NULL || (recoA && recoA->valor < recoB->valor)) {
      lista_insertar_final(&resultado, recoA->valor);
      recoA = recoA->sig;
    } else {
      lista_insertar_final(&resultado, recoB->valor);
      recoB = recoB->sig;
    }
  }
  return resultado;
}

13.6 Detectar ciclos (Floyd)

El algoritmo de Floyd (tortuga y liebre) recorre la lista con dos punteros a velocidades distintas. Si hay un ciclo, ambos punteros se encontrarán; de lo contrario, el puntero rápido llegará a NULL. Detectar ciclos evita loops infinitos y fugas de memoria en listas circulares no deseadas.

bool lista_tiene_ciclo(const Lista *lista) {
  const Nodo *lento = lista->cabeza;
  const Nodo *rapido = lista->cabeza;
  while (rapido && rapido->sig) {
    lento = lento->sig;
    rapido = rapido->sig->sig;
    if (lento == rapido) return true;
  }
  return false;
}
Retornar