一般的なチェーンテーブル操作

1.単鎖表の逆順
逆順出力チェーンテーブルを含み、3つの方式があり、1つ目は操作用スタックの方式で、チェーンテーブルをスタックにロードし、新しいチェーンテーブルを作成して出力する.2つ目は、ヘッドノードが挿入されず、ヘッドノードが挿入された後です.3つ目は対称交換であり,チェーンテーブルを中心ノードを中心として対称交換を行う.
2.連結順序チェーンテーブル
秩序チェーンテーブルのマージには2つの方法があり、1つは新しいチェーンテーブルを新規作成し、2つの秩序チェーンテーブルの対応するノードの大きさを比較し、1回に新規チェーンテーブルに追加し、2つのチェーンテーブルが等しくない場合、最後に長いものを新規チェーンテーブルの末尾に追加します.第2の方式は第1の方式と似ているが、この方式はチェーンテーブルを新設せず、元のチェーンテーブルのポインタを修正して修正するだけで、その他は第1の方式と同じである.
3.2つの単一チェーンテーブルが交差しているかどうかを判断し、交差している場合は、最初の交差ノードを返します.
単一チェーンテーブルの交差は、最後にY型のチェーンテーブルに違いない.すなわち、チェーンテーブルは最後に共通の部分(少なくとも1つのノード)があるに違いない.まず、2つの単一チェーンテーブルが交差しているかどうかを判断することは、2つのチェーンテーブルを遍歴し、遍歴の最後のノードが等しいかどうかを見ることであり、等しい場合は、交差チェーンテーブルである.第2のステップは、第1の交差するノードを探し出すことであり、この過程には2つの方法がある:1、長いチェーンテーブルでabs(長いチェーンテーブル-短いチェーンテーブル)を減算し、それから短いチェーンテーブルの頭から、長いチェーンテーブルの減算の対応する位置からチェーンテーブル要素の遍歴比較を行い、第1の等しい要素は交差チェーンテーブルの交点である.2、2つのチェーンテーブルの要素をすべて2つのスタックに入れて、それからスタックを比較します.これはチェーンテーブルの末尾から2つのチェーンテーブルを順番に遍歴して、最初の等しくない要素を見つけて、この要素の前の要素は彼らの交点です.
4.単一チェーンテーブルにループがあるかどうかを判断し、ループがある場合はループに入る最初のノードに戻る
チェーンテーブルにリングがあるかどうかを判断するには、速いポインタを設定することができ、例えばポインタa,b,aの前にさらに、bが2つ前進し、bの最後の要素がnullであれば、リングがないことを証明し、a=bであれば、チェーンテーブルにリングがあることを証明する.
ループに最初に入ったノードを返すにはどうすればいいですか?ノードのアドレスをhashし,チェーンテーブルを巡り,アドレスが等しいノードがあるか否かを検出する.もう1つの方法はjavaでsetまたはhashMap構造を採用し、最初に構造長を増加させない要素が現れたとき、この要素はリングに入る最初のノードである.
5.単一チェーンテーブルの中間の要素を探し出す
速いポインタを設定して、速いポインタは前に2つの位置を歩いて、遅いポインタは前に1つの位置を歩いて、速いポインタがチェーンテーブルの尾まで歩いた時、遅いポインタはちょうどチェーンテーブルの真ん中にあります;
6.単一チェーンテーブルの最後からK番目の要素を削除する
2つのポインタp 1とp 2を設定し、p 1はチェーンテーブルの最初のノードを指し、p 2はk+1番目のノードを指し、2つのポインタは同時に前進し、p 2がチェーンテーブルの最後に到着したとき、p 1は最後からk+1番目のノードを指し、p 1の後ろのノードを削除すればよい.
7.単一チェーンテーブルの指定ノードの前にノードを挿入する
現在のノードをコピーすると、チェーンテーブルに同じ接続ノードが2つあり、挿入ノードで前のノードを上書きして挿入を実現します.
8.ジョセフリング
問題の要求から私たちはこの問題を直感的に感知することができなくて、1つのテストの例から始めなければなりません.0,1,2,3,4の5つの数字が円を構成すると仮定し,0から3番目の数字を削除するたびに削除すると,削除される最初の4つの数字は2,0,4,1,3である.これは有名なジョセフ環問題で、それは簡潔な数学の公式を持っていますが、私たちが深い数学の素養と数学の感度を持っていない限り、一気に考えるのは難しいです.プログラマーの最も一般的な方法は、私たちのコードをテスト例に合格させるためにあらゆる方法を尽くすことです.円である以上、リングチェーンテーブルを連想します.

int LastRemaining(unsigned int n, unsigned int m)
{
    if(n < 1 || m < 1)
    {
         return -1;
    }

    unsigned int i = 0;

    lisg<int> numbers;
    for(i = 0; i < n; ++i)
    {
         numbers.push_back(i);
    }

    list<int> :: iterator current = numbers.begin();
    while(numbers.size() > 1)
    {
        for(int i = 1l i < m; ++i)
        {
              current++;
              if(current == numbers.end()){
                    current = number.begin();
              }
         }

         list<int> :: iterator next = ++current;
         if(next == numbers.end()){
               next = numbers.begin();
         }

         --current;
         numbers.erase(current);
         current = next;
    }

    return *(current);
}

       std :: list         ，   std :: list           ，                    ，           。 

            ，        ：

int LastRemaining(unsigend int n, unsigned int m)
{
    if(n < 1 || m < 1)
    {
          return -1;
    }

    int last = 0;
    for(int i = 2; i <= n; ++i)
   {
       last = (last + m) % i;
   }

   return last;
}