単一のチェーンリストを逆順にリスト

Question

私は正しい専門用語を使用したいと思います。 私は一本鎖のリストを作った。

class MyStack 
{ 
    public Node Initial { get; set; } 

    public MyStack() 
    { 
     Initial = null; 
    } 

    public void Push(int data) 
    { 
     var node = new Node { Data = data, Next = Initial }; 
     Initial = node; 
    } 

    public int Pop() 
    { 
     int res = Initial.Data; 
     Initial = Initial.Next; 
     return res; 
    } 

    public int Sum() 
    { 
     int sum = 0; 
     Node currentNode = Initial; 
     while (currentNode != null) 
     { 
      sum += currentNode.Data; 
      currentNode = currentNode.Next; 
     } 
     return sum; 
    } 
    public int Count() 
    { 
     int count = 0; 
     Node currentNode = Initial; 
     while (currentNode != null) 
     { 
      count++; 
      currentNode = currentNode.Next; 
     } 
     return count; 
    } 

    public void PrintAll() 
    {  
     Node currentNode = Initial; 
     while(currentNode != null) 
     { 
      Console.WriteLine("tmp.Data = " + currentNode.Data); 
      currentNode = currentNode.Next; 
     } 
    } 
} 
public class Node 
{ 
    public int Data; 
    public Node Next; 
} 

あなたはこのような何かを行うことができます意味：

var s = new MyStack(); 
    s.Push(5); 
    s.Push(3); 
    s.Push(7); 
    s.PrintAll(); 
    Console.WriteLine("Sum: " + s.Sum()); 
    Console.WriteLine("Count: " + s.Count()); 

は今、私が試してみて、逆の方法を作りたいです。これは動作しているようです：

public void Reverse() 
{ 
    Node predesesor, location; 
    location = Initial; 
    predesesor = null; 
    while(Initial != null) 
    { 
     Initial = Initial.Next; 
     location.Next = predesesor; 
     predesesor = location; 
     location = Initial; 
    } 
    Initial = predesesor; 
} 

私はそれがどのように動作するかはほとんど分かりません。維持するのは難しいでしょう。 それは他の何よりもハックのようです。

助けてもらえますか？

Answer 1

私にはハックのようには見えないし、維持するために何があるのか​​わからない（それは正しいかどうか、それ以外に何をするのか？）。それがどのように機能するかを把握したい場合は、紙面上の各ステップを「実行」します。リストを描画し（例えば、1→3→5→7→9→NULL）、いつでもすべてのノードが指し示している場所をマークし、「シングルステッピング」を開始します。

単独でリンクされたリストを元に戻すよりクリーンな方法は考えられませんでした。現在のノードと直前のノードとの間のリンクを逆転させるには、次のノードへの参照が必要です（ループの先頭にあるInitial）。それ以外の場合は元のリストに移動することはできません。

あなたができることは、変数のスペルを修正し、おそらくループ自体で最初の変数を使用しないようにします（各変数の役割がより明確になるように3番目の変数を使用します）最後にリスト。だから、

、すべてのすべて：

public void Reverse() { 
    Node current = Initial, previous = null; 
    while (current) { 
     Node next = current.Next; 
     current.Next = previous; 
     previous = current; 
     current = next; 
    } 
    Initial = previous; 
} 

Answer 2

一つの解決策は、二重リンクリストにそれを回す、その後、前のノードのプロパティを使用して逆方向に動作するように次のようになります。

public class Node 
{ 
    public int Data; 
    public Node Next; 
    public Node Previous; 
} 

あなたがしたい場合は、フレームワークでalready二重リンクリストがありますあなた自身の努力を惜しまない。

Answer 3

あなたはrecursivlyそれを行うことができます。

a->b->c->d 

    a->null 
    b->null 
     c->null 
     c<-d 
    b<-c 
    a<-b 

a<-b<-c<-d 

public void Reverse() 
{ 
    Reverse(Initial); 
} 

private void Reverse(Node node) 
{ 
    if(node != null && node.Next != null) 
    { 
     //go deeper 
     Reverse(node.Next); 
     //swap 
     node.Next.Next = node 
     node.Next = null; 
    } 
} 

Answer 4

あなたはすべての開発者の価値tuppenceが分かるであろうし、 "場所にリバース" "nreverseの" それを呼び出す場合や、それはハックではなく古典的なアルゴリズムです。

誤って綴られた変数の名前を変更することを除いて、メンテナンスは必要ありません。

Answer 5

車輪を改造するのではなく、既に何かがある場合はsomething from .Net Frameworkを使用することができます。

たとえば、私はLinkedListNodeでLinkedListをここに取ります。他の場合は、おそらくQueueまたはStackとすることができます。

Answer 6

次のコードはもう少し直感的かもしれない：

public void Reverse() 
{ 
    MyStack reverse = new MyStack(); 
    while (Initial != null) 
    { 
     reverse.Push(this.Pop()); 
    } 
    Initial = reverse.Initial; 
} 

（リバースがMyStackクラスのメンバメソッドです）。

もちろん、元のコードと比べて2倍のスペースが必要です。

Answer 7

stack s1 
s1.push_front(...) 
... 
s1.push_front(...) 

///////////////////////////////////////////////////////////////////// /////////////

void reverse(stack& to,stack_or_list& s) 
    while(!s.empty()){ 
     to.push_front(s.pop_front()); 
    } 
} 

今to.pop_frontsのシリーズは、あなたが望むものを必要stack_or_list

取得します：ニーズにpop_front空 ：push_front、pop_front

を