Java：リンクリストをチャンクで

Question

リンクリストの先頭にあり、k個のノードシーケンスを逆にするように求められたら、どうすればJavaでこれを行うことができますか？たとえばk = 3のa->b->c->d->e->f->g->hはc->b->a->f->e->d->h->g->f

となります。一般的なヘルプや疑似コードも大変ありがとうございます。ありがとう！

Answer 1

kがかなり小さいと予想される場合、私は単純なことをします。リンクされたリストであるという事実を無視して、各サブシーケンスを逆の配列型のものとして扱います。

したがって、リンクリストのノードクラスがNode<T>の場合は、kのNode<?>[]を作成します。各セグメントについて、配列リストにkNodesをロードし、単純なループで要素を逆転させます。for擬似コード：

利点：わかりやすく、O（N）性能は、わかりやすい反転アルゴリズムを利用しています。

短所：（あなたは、セグメントごとにそれを再利用することができるので、一度だけ）k -sized配列を必要と

はまたNodeが保持しているオブジェクトのみ、これは各Nodeがリストに移動していないことを意味していることに注意してください。これは、各Nodeが以前に保持していたアイテムとは異なるアイテムを保持することになることを意味します。これはあなたの必要に応じてうまくいくかもしれません。

Answer 2

これはかなり高レベルですが、私はそれがいくつかの指針を与えると思います。

私はvoid swap3(Node first, Node last)のようなヘルパーメソッドを持ち、リストの任意の位置に3つの要素をとり、それらを逆にします。これは難しいことではなく、再帰的に実行できます（外側の要素を交換し、リストのサイズが0または1になるまで内側の要素に再帰します）。これを考えると、再帰を使用している場合は、これを一般的にswapK()に一般化することができます。

これが完了すると、リンクされたリストに沿って歩いて、kノードごとにswapK()と電話することができます。リストのサイズがkで割り切れない場合は、その最後のビットを交換しないでください。または最後のlength%kノードを交換技法を使用して逆転させることもできます。

Answer 3

TIME O（n）;スペース反転O（1）

リスト反転の通常の要件は、O（n）時間とO（1）時間に行うことです。これにより、再帰またはスタックまたは一時的な配列（K == nならどうなるでしょうか）などが除かれます。 したがって、ここでの解決策は、Kの因数を考慮してインプレースリバーサルアルゴリズムを変更することです。 Kの代わりにdistを使用します。

単純なインプレースリバーサルアルゴリズムは次のとおりです。3つのポインタを使用してリストを所定の位置に移動します。bは新しいリストの先頭を指します。 cは未処理リストの移動ヘッドをポイントします。 bとcの間の交換を容易にするためにa。

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; 
} 

がchunkReverseアルゴリズムsimpleReverseアルゴリズムを変換するには、次の操作を行います

1]最初のチャンクを逆にした後、bにheadを設定します。 headは、結果として得られるリストの永続的な頭です。

2]他のすべてのチャンクでは、tail.nextからbに設定します。 bがちょうど処理されたチャンクの先頭であることを思い出してください。

いくつかの他の詳細：

3]リストは、一つまたは少数のノードを有するか、またはDISTが1以下であり、処理せずにリストを返す場合。

4]カウンタcntを使用して、distの連続したノードが逆転した時刻を記録します。

5]処理されたばかりのチャンクの末尾をトラッキングするには変数tailを使用し、処理されるチャンクの末尾をトラッキングするにはtmpを使用します。

6]チャンクが処理される前に、頭が尾になるようにバインドされていることに注目してください。最初のノードはtmpです。これは一時的なテールです。

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

など。コモン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))))) 

他の方法 などの。 F＃でスタックを使用する

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

スタックを使用して、リストからk個のアイテムを繰り返し削除し、それらをスタックにプッシュしてポップし、それらを所定の場所に追加します。それが最良の解決策であるかどうかは分かりませんが、スタックは物を反転させる適切な方法を提供します。キューがあるリストではなく、これが機能することにも注意してください。 単にデキューk個のアイテム、スタックにプッシュ、スタックからそれらをポップし、それらをキュー:)

Answer 6

この実装では、反復子クラスを使用します。

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); 
}