Java: inversión de LinkedList en fragmentos

Question

Si se le proporciona el encabezado de una lista vinculada, y se le pide que invierta cada una de las ksecuencias de nodos, ¿cómo podría hacerse esto en Java? por ejemplo, a->b->c->d->e->f->g->h con k = 3 sería c->b->a->f->e->d->h->g->f

¡Cualquier ayuda general o incluso pseudocódigo sería muy apreciada! ¡Gracias!

Answer 1

Si se espera que k sea razonablemente pequeño, me limitaré a lo más simple: ignorar el hecho de que se trata de una lista vinculada, y tratar cada subsecuencia como una serie de elementos que se revertirán.

Por lo tanto, si la clase de nodo de su lista vinculada es Node<T>, cree un Node<?>[] del tamaño k. Para cada segmento, cargue kNodes en la lista de arreglos, luego solo invierta sus elementos con un simple bucle for. En pseudocódigo:

// reverse the elements within the k nodes 
for i from 0 to k/2: 
    nodeI = segment[i] 
    nodeE = segment[segment.length-i-1] 
    tmp = nodeI.elem 
    nodeI.elem = nodeE.elem 
    nodeE.elem = tmp 

Pros: rendimiento muy simple, O (N), se aprovecha de un algoritmo de marcha atrás fácilmente reconocible.

Contras: Requiere una matriz -sized k (sólo una vez, ya que se puede volver a utilizarlo por segmento)

También tenga en cuenta que esto significa que cada Node no se mueve en la lista, sólo los objetos del Node sostiene . Esto significa que cada Node terminará sosteniendo un elemento diferente del que tenía anteriormente. Esto podría estar bien o no, según sus necesidades.

Answer 2

Esto es bastante alto nivel, pero creo que le dará alguna orientación.

Tendría un método de ayuda como void swap3(Node first, Node last) que toman tres elementos en una posición arbitraria de la lista y los invierte. Esto no debería ser difícil, y podría hacerse de manera recursiva (intercambie los elementos externos, recurse en los elementos internos hasta que el tamaño de la lista sea 0 o 1). Ahora que lo pienso, puedes generalizar esto en swapK() fácilmente si estás utilizando recursividad.

Una vez hecho esto, puede simplemente caminar a lo largo de su lista vinculada y llamar al swapK() cada k nodos. Si el tamaño de la lista no es divisible por k, puede simplemente no intercambiar ese último bit, o invertir los últimos nodos length%k usando su técnica de intercambio.

Answer 3

TIME O (n); SPACE O (1)

Un requisito habitual de la inversión de lista es que lo haga en el tiempo O (n) y en el espacio O (1). Esto elimina la recursión o pila o matriz temporal (¿qué pasa si K == n?), Etc. Por lo tanto, el desafío aquí es modificar un algoritmo de inversión in situ para tener en cuenta el factor K. En lugar de K uso dist para la distancia.

Aquí hay un algoritmo de inversión en el lugar simple: utilice tres punteros para recorrer la lista en su lugar: b para señalar el encabezado de la nueva lista; c para apuntar al cabezal móvil de la lista no procesada; a para facilitar el intercambio entre b y c.

A->B->C->D->E->F->G->H->I->J->L //original 
A<-B<-C<-D E->F->G->H->I->J->L //during processing 
     ^^
      | | 
      b c 
`a` is the variable that allow us to move `b` and `c` without losing either of 
    the lists. 

Node simpleReverse(Node n){//n is head 
if(null == n || null == n.next) 
    return n; 
Node a=n, b=a.next, c=b.next; 
a.next=null; b.next=a; 
while(null != c){ 
    a=c; 
    c=c.next; 
    a.next=b; 
    b=a; 
} 
return b; 
} 

Convertir el algoritmo simpleReverse a un algoritmo de chunkReverse, hacer lo siguiente:

1] Después de la inversión de la primera porción, ajuste head a b; head es el jefe permanente de la lista resultante.

2] para todos los demás fragmentos, establezca tail.next en b; recuerde que b es el encabezado del fragmento recién procesado.

algunos otros detalles:

3] Si la lista tiene uno o menos nodos o el dist es 1 o menos, a continuación, devolver la lista sin procesamiento.

4] utiliza un contador cnt para rastrear cuando dist nodos consecutivos se han invertido.

5] usa la variable tail para rastrear la cola del fragmento recién procesado y tmp para rastrear la cola del fragmento que se está procesando.

6] observe que antes de que se procese un trozo, su cabeza, que se convertirá en su cola, es el primer nodo con el que se encuentra: así que, configúrelo en tmp, que es una cola temporal.

public Node reverse(Node n, int dist) { 
    if(dist<=1 || null == n || null == n.right) 
     return n; 
    Node tail=n, head=null, tmp=null; 
    while(true) { 
     Node a=n, b=a.right; n=b.right; 
     a.right=null; b.right=a; 
     int cnt=2; 
     while(null != n && cnt < dist) { 
      a=n; n=n.right; a.right=b; b=a; 
      cnt++; 
     } 
     if(null == head) head = b; 
     else { 
      tail.right=b;tail=tmp; 
     } 
     tmp=n; 
     if(null == n) return head; 
     if(null == n.right) { 
      tail.right=n; 
      return head; 
     } 
    }//true 
    } 

Answer 4

E.g. por Common Lisp

(defun rev-k (k sq) 
    (if (<= (length sq) k) 
     (reverse sq) 
     (concatenate 'list (reverse (subseq sq 0 k)) (rev-k k (subseq sq k))))) 

otra manera P. ej por F # utilizar Pila

open System.Collections.Generic 
let rev_k k (list:'T list) = 
    seq { 
    let stack = new Stack<'T>() 
    for x in list do 
     stack.Push(x) 
     if stack.Count = k then 
     while stack.Count > 0 do 
      yield stack.Pop() 
    while stack.Count > 0 do 
     yield stack.Pop() 
    } 
    |> Seq.toList 

Answer 5

Utilice una pila y de forma recursiva eliminar k artículos de la lista, los empujan a la pila a continuación, el pop y agregarlos en su lugar. No estoy seguro de si es la mejor solución, pero las pilas ofrecen una forma adecuada de invertir las cosas. Tenga en cuenta que esto también funciona si en lugar de una lista tiene una cola. k artículos Simplemente dequeue, empujarlos a la pila, el pop de la pila y poner en cola ellos :)

Answer 6

Esta aplicación utiliza la clase ListIterator:

LinkedList<T> list; 
//Inside the method after the method's parameters check 
ListIterator<T> it = (ListIterator<T>) list.iterator(); 
ListIterator<T> reverseIt = (ListIterator<T>) list.listIterator(k); 

for(int i = 0; i< (int) k/2; i++) 
{ 
    T element = it.next(); 
    it.set(reverseIt.previous()); 
    reverseIt.set(element); 
}