Java: inversione di LinkedList in blocchi

Question

Se viene fornita la testa di un elenco collegato e viene chiesto di invertire ogni k sequenza di nodi, come potrebbe essere fatto in Java? ad esempio, a->b->c->d->e->f->g->h con k = 3 sarebbe c->b->a->f->e->d->h->g->f

Qualsiasi aiuto generale o addirittura pseudocodice sarebbe molto apprezzato! Grazie!

Answer 1

Se si prevede che k sia ragionevolmente piccolo, vorrei semplicemente fare la cosa più semplice: ignorare il fatto che si tratta di un elenco collegato e considerare ogni sottosequenza come una cosa di tipo array di cose da invertire.

Quindi, se la classe di nodo dell'elenco collegato è un Node<T>, creare un Node<?>[] di dimensioni k. Per ogni segmento, carica kNodes nell'elenco di array, quindi basta invertire i loro elementi con un semplice ciclo for. In pseudocodice:

// 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 

Pro: prestazioni molto semplice, O (N), si avvale di un algoritmo di inversione facilmente riconoscibile.

Contro: richiede un allineamento -sized k (solo una volta, dal momento che è possibile riutilizzarlo per segmento)

noti inoltre che questo significa che ogni Node non si muove nella lista, solo gli oggetti della Node stive . Ciò significa che ogni Node finirà per contenere un elemento diverso da quello in cui era tenuto in precedenza. Questo potrebbe andar bene o no, a seconda delle tue esigenze.

Answer 2

Questo è piuttosto di alto livello, ma penso che fornirà una guida.

Avrei un metodo di supporto come void swap3(Node first, Node last) che accetta tre elementi in una posizione arbitraria dell'elenco e li inverte. Questo non dovrebbe essere difficile, e potrebbe essere fatto in modo ricorsivo (scambia gli elementi esterni, ricorri sugli elementi interni fino a quando la dimensione della lista è 0 o 1). Ora che ci penso, potresti generalizzare questo in swapK() facilmente se usi la ricorsione.

Una volta fatto, puoi semplicemente camminare lungo l'elenco collegato e chiamare swapK() ogni nodo . Se la dimensione della lista non è divisibile per k, potresti semplicemente non scambiare quell'ultimo bit o invertire gli ultimi nodi length%k usando la tua tecnica di scambio.

Answer 3

TIME O (n); SPACE O (1)

Un normale requisito di inversione dell'elenco è che lo si fa nel tempo O (n) e nello spazio O (1). Questo elimina ricorsione o stack o array temporaneo (cosa succede se K == n?), Ecc. Quindi la sfida qui è modificare un algoritmo di inversione sul posto per tenere conto del fattore K. Invece di K io uso dist per la distanza.

Ecco un semplice algoritmo di inversione sul posto: utilizzare tre puntatori per spostare l'elenco sul posto: b in modo che punti all'inizio del nuovo elenco; c per indicare la testa mobile dell'elenco non elaborato; a per facilitare lo scambio tra b e 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; 
} 

Per convertire il simpleReverse algoritmo per un chunkReverse algoritmo, do seguente:

1] Dopo l'inversione primo blocco, impostare head a b; head è il capo permanente dell'elenco risultante.

2] per tutti gli altri blocchi, impostare tail.next su b; ricorda che b è il capo del blocco appena elaborato.

qualche altro dettaglio:

3] Se la lista ha una o un minor numero di nodi o il dist è 1 o meno, per poi tornare alla lista senza elaborazione.

4] utilizzare un contatore cnt per rintracciare quando i nodi consecutivi sono stati invertiti dist.

5] utilizzare la variabile tail per tracciare la coda del blocco appena elaborato e tmp per tracciare la coda del blocco in elaborazione.

6] si noti che prima che un blocco venga elaborato, è la testa, che è destinata a diventare la coda, è il primo nodo che si incontra: quindi, impostarlo su tmp, che è una coda temporanea.

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. da 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))))) 

altro modo Ad es da F # usa Stack

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

Utilizzare una pila e in modo ricorsivo rimuovere gli elementi k dalla lista, li spingono alla pila poi farli scoppiare e aggiungerli al loro posto. Non sono sicuro che sia la soluzione migliore, ma gli stack offrono un modo corretto di invertire le cose. Si noti che questo funziona anche se al posto di una lista si avesse una coda. articoli K Semplicemente dequeue, spingerli allo stack, li pop dalla pila e accodare loro :)

Answer 6

Questa implementazione utilizza classe 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); 
}