6

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

一般的なヘルプや擬似コードでさえも大歓迎です！ありがとう！

4

6 に答える 6

4

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

したがって、リンクリストのノードクラスがである場合は、サイズNode<T>のを作成します。セグメントごとに、配列リストにロードしてから、単純なループで要素を逆にします。擬似コードの場合：Node<?>[]kk Nodesfor

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

長所：非常にシンプルなO（N）パフォーマンスで、簡単に認識できる反転アルゴリズムを利用します。

短所：kサイズの配列が必要です（セグメントごとに再利用できるため、1回だけ）

Nodeまた、これは、それぞれがリスト内で移動せず、Node保持しているオブジェクトのみが移動することを意味することに注意してください。これは、それぞれNodeが以前とは異なるアイテムを保持することになることを意味します。必要に応じて、これで問題ない場合もあります。

于 2012-04-22T21:45:10.093 に答える
1

これはかなりハイレベルですが、ある程度のガイダンスになると思います。

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

それが完了したら、リンクリストに沿って歩き、swapK()すべてのkノードを呼び出すことができます。リストのサイズがで割り切れない場合は、最後のビットをスワップしないか、スワップ手法を使用して最後のノードをk逆にすることができます。length%k

于 2012-04-22T21:33:48.570 に答える
1

時間O（n）; スペースO（1）

リスト反転の通常の要件は、O（n）時間とO（1）空間で行うことです。これにより、再帰、スタック、または一時配列（K == nの場合はどうなりますか？）などが排除されます。したがって、ここでの課題は、Kファクターを考慮してインプレース反転アルゴリズムを変更することです。距離Kに使う代わりに。dist

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

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

simpleReverseアルゴリズムをアルゴリズムに変換するにはchunkReverse、次のようにします。

1]最初のチャンクを反転した後、;に設定headします。結果のリストの永続的なヘッドです。bhead

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

その他の詳細：

3]リストのノードが1つ以下の場合、または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
  }
于 2012-04-22T23:27:51.433 に答える
1

例：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)))))

他の方法、たとえばF＃では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
于 2012-04-22T23:39:47.480 に答える
0

スタックを使用して、リストからk個のアイテムを再帰的に削除し、それらをスタックにプッシュしてから、ポップして所定の位置に追加します。それが最善の解決策であるかどうかはわかりませんが、スタックは物事を逆転させる適切な方法を提供します。これは、リストの代わりにキューがある場合にも機能することに注意してください。k個のアイテムをデキューし、スタックにプッシュし、スタックからポップして、エンキューするだけです:)

于 2012-04-23T03:38:17.390 に答える
0

この実装では、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);
}
于 2012-04-23T15:08:34.603 に答える