¿Cómo dividir recursivamente una lista enlazada después de k nodos en C++?

22 Jul, 2023 Programación 0

Tengo una lista enlazada ordinaria con:

struct node{
  int info;
  node* next;
};

Necesito escribir una función recursiva que divida en 2 una lista enlazada dada pasada por referencia después de k elementos, dejando los primeros k nodos en esta lista y devolviendo la segunda lista con el resto de los nodos.

Mi solución iterativa se ve así:

node* split(node*&L, int k){
   node* M;
   node* head = L;
   while(k>1){
      head=head->next;
      k--;
   }
   M = head->next;
   head->next = NULL;
   return M;
}

Output:
L: 1 2 3 4 5 6 
después de dividir con: k = 3
L: 1 2 3 
M: 4 5 6

Lo cual parece funcionar bien. Ahora realmente no puedo pensar en una solución recursiva para esto. Estaba intentando con:

node* splitL(node*&L, int k){
   if(!L) return 0;
   if(k<=1){
      node* x = L->next;
      L->next =  NULL;
      return x;
   }
   L->next = splitL(L->next, k-1);
   return L;
}

Lo cual es obviamente incorrecto porque está devolviendo x en L->next, por lo que ambas listas se convierten en 1 2 3 4 5 6.

¿Cómo puedo escribir una función recursiva para esto? Los parámetros y el tipo de retorno deben mantenerse iguales. También sería genial si alguien pudiera explicar cómo puedo traducir mi solución iterativa en una solución recursiva.

davy.ai

July 22, 2023 at 1:17 am

Para escribir una función recursiva para dividir una lista enlazada en dos después de k nodos, podemos usar el siguiente enfoque:

Caso base: Si el nodo actual es NULL, entonces retornar NULL.
Caso recursivo: Si k es mayor que 1, llamar a la función recursiva con el siguiente nodo y k-1. Si k es igual a 1, entonces hemos llegado al nodo después del cual necesitamos dividir. Establecemos el puntero next del nodo actual a NULL y retornamos el siguiente nodo.
En la función principal, podemos llamar a esta función recursiva con el nodo head y k-1 (ya que necesitamos dividir después de k nodos, incluyendo el primer nodo).

La función recursiva se vería así:

node* splitL(node*& L, int k){
    if(!L) return 0; // caso base
    if(k==1){
        node* M = L->next; // el siguiente nodo es el comienzo de la segunda lista
        L->next = NULL; // terminamos la primera lista
        return M; // retornamos la segunda lista
    }
    return splitL(L->next, k-1); // caso recursivo
}

Para traducir la solución iterativa a una recursiva, necesitamos pensar en cómo podemos recorrer la lista enlazada de manera recursiva. En la solución iterativa, usamos un bucle while para recorrer la lista hasta llegar al k-ésimo nodo.

En la solución recursiva, podemos recorrer la lista llamando recursivamente a la función con el siguiente nodo como parámetro de entrada. Luego podemos verificar si hemos llegado al k-ésimo nodo o no, y retornar los valores correspondientes apropiadamente.

Así es como la solución iterativa puede ser traducida a una solución recursiva:

node* split(node*& L, int k){
    if(k == 1){
        node* M = L->next; // el siguiente nodo es el comienzo de la segunda lista
        L->next = NULL; // terminamos la primera lista
        return M; // retornamos la segunda lista
    }
    return split(L->next, k-1); // llamamos recursivamente a split con el siguiente nodo
}

Tanto la solución iterativa como la solución recursiva tienen la misma salida para la entrada dada.

Answer

davy.ai

July 22, 2023 at 1:17 am
Para escribir una función recursiva para dividir una lista enlazada en dos después de k nodos, podemos usar el siguiente enfoque:
1. Caso base: Si el nodo actual es NULL, entonces retornar NULL.
2. Caso recursivo: Si k es mayor que 1, llamar a la función recursiva con el siguiente nodo y k-1. Si k es igual a 1, entonces hemos llegado al nodo después del cual necesitamos dividir. Establecemos el puntero next del nodo actual a NULL y retornamos el siguiente nodo.
3. En la función principal, podemos llamar a esta función recursiva con el nodo head y k-1 (ya que necesitamos dividir después de k nodos, incluyendo el primer nodo).
La función recursiva se vería así:
```
node* splitL(node*& L, int k){
    if(!L) return 0; // caso base
    if(k==1){
        node* M = L->next; // el siguiente nodo es el comienzo de la segunda lista
        L->next = NULL; // terminamos la primera lista
        return M; // retornamos la segunda lista
    }
    return splitL(L->next, k-1); // caso recursivo
}
```
Para traducir la solución iterativa a una recursiva, necesitamos pensar en cómo podemos recorrer la lista enlazada de manera recursiva. En la solución iterativa, usamos un bucle while para recorrer la lista hasta llegar al k-ésimo nodo.

En la solución recursiva, podemos recorrer la lista llamando recursivamente a la función con el siguiente nodo como parámetro de entrada. Luego podemos verificar si hemos llegado al k-ésimo nodo o no, y retornar los valores correspondientes apropiadamente.

Así es como la solución iterativa puede ser traducida a una solución recursiva:
```
node* split(node*& L, int k){
    if(k == 1){
        node* M = L->next; // el siguiente nodo es el comienzo de la segunda lista
        L->next = NULL; // terminamos la primera lista
        return M; // retornamos la segunda lista
    }
    return split(L->next, k-1); // llamamos recursivamente a split con el siguiente nodo
}
```
Tanto la solución iterativa como la solución recursiva tienen la misma salida para la entrada dada.

Comments are closed.

es.davy.ai

¿Tienes una pregunta?

¿Cómo dividir recursivamente una lista enlazada después de k nodos en C++?

Answer

davy.ai