performance - nodos - Algoritmo para encontrar el puntero al nodo M Pasos para alinear en una lista enlazada individualmente

nodos en java

Question

Supongamos que hay una lista individualmente vinculada cuya longitud es desconocida. Queremos encontrar el nodo con M pasos a la cola.

Por ejemplo, la lista individual es así: (A) -> (B) -> (C) -> (X) -> (Y) y M = 2. Entonces la salida debe ser un puntero a (C).

Cuando me enfrento a este cuestionario, mi primera reacción es atravesar la lista enlazada individualmente para obtener la longitud N. Luego, recorrer la segunda por separado, pero solo adelantar los pasos NM-1. La complejidad del tiempo es O (n) y la complejidad del espacio es O (1).

Luego, tengo el desafío de encontrar una solución para hacerlo de una sola vez. La solución es tener dos punteros. El segundo puntero está M pasos detrás del primer puntero. Estos dos indicadores avanzan al mismo ritmo. Cuando el primer puntero alcanza la cola, el segundo puntero es el resultado.

Después de una profunda reflexión sobre esta cuestión, realmente no creo que la segunda solución "engañosa" sea superior a la primera. Es unidireccional, pero también implica asignaciones de puntero 2 * NM.

¿Alguna idea sobre esta pregunta? ¿Hay alguna otra solución que sea realmente más rápida?

Answer 1

Aparte de su algoritmo propuesto de estilo de conteo, podría usar una función recursiva similar a:

int getNumNodesAfter(Node *node){
   if( node->next == NULL ){
      return 0;
   }else{
      return getNumNodesAfter(node->next) + 1;
   }
}

Por supuesto, querrá encontrar una buena manera de almacenar el nodo en cuestión cuando la función devuelva el número que está buscando.

(Editar: esto probablemente no sea más eficiente que el algoritmo de conteo, solo una alternativa)

Sin embargo, la respuesta real a la pregunta es: su estructura de datos (lista individualmente vinculada) no facilita una implementación rápida de la operación que desea realizar en ella, por lo que debe elegir una nueva estructura de datos.

Answer 2

Creo que algo un poco mejor sería algo así como:

FindNFromEnd(head, n)
    counter = 0;
    first = head
    firstplusn = head
    while (head.next != null)
        counter++
        head = head.next

        if counter == n
            first = firstplusn
            firstplusn = head
            counter = 0

     while counter < n
         counter++
         first = first.next

     return first

por ejemplo, si n = 3, se vería algo así como:

    0   1   2   3   4   5   6   7
1   FNH
2   FN  H   
3   FN      H
1   F           NH 
2   F           N   H
3   F           N       H
1   F           N           H
2               F           N   H
---
3                  [F]

Así que F realiza un seguimiento del contador de cabeceras - N, N realiza un seguimiento del contador de cabeceras, y solo necesita hacer algo (N + M + N / M) en lugar de O (2 * N - M).

Answer 3

Deberías usar un buffer circular

Asigne un conjunto de punteros M + 1 y complete el puntero (i mod M + 1) th para cada nodo a través de la lista. Cuando llegue al final, busque M en la matriz (envolviendo si es necesario).

¡De esa manera, solo tienes N escribe!

Aquí hay un programa de ejemplo de trabajo pirateado en c ++

node* get_Mth_from_end(node* head, int m)
{
  int pos = 0;
  node** node_array = new node*[m + 1];
  node_array[0] = head;
  while (node_array[(pos + 1) % (m + 1)] = node_array[pos % (m + 1)]->next)
     pos++;
  if (pos < m)
  {
     delete[] node_array;
     return NULL;
  }
  pos = pos - m;
  if (pos < 0)
     pos = pos + m + 1;
  node* retval = node_array[pos];
  delete[] node_array;
  return retval;
}

Esto debe verificarse por 1 error. La sintaxis de mi puntero también puede estar un poco descuidada, pero la idea está ahí.

Answer 4

Me gusta la sugerencia recursiva. Sin embargo, no creo que aumente el rendimiento sobre el algoritmo de doble puntero en la pregunta.

Rubancache tiene razón en que la estructura de datos no admite operaciones más rápidas. Está hecho para cruces lentos pero con tiempos de inserción rápidos.

Answer 5

Se puede hacer con asignaciones de puntero N + 4M y espacio de registro (M) (bueno, espacio extra, su lista ya ocupa N). Así es como (la idea es la misma idea que usan las personas en los depuradores de devolución). El pseudocódigo sigue, donde M <2 ^ m, y p es un buffer circular de longitud m

for (n=0, front = 0; p[front] != end; ++n, ++p[front]) {
  for (j = 0; j < m; ++j)
    if (n % j = 0)
      ++ front
  front = front % m
}
front = (front-1) % m
for (j = M; j < n-2^m - (n mod 2^m); ++j)
  ++p[front]

p [front] ahora es tu respuesta