ループを持つリンクリストを反転する

Question

リンクリストにループがある場合（つまり、最後のノードが中間のノードにリンクされている場合）、リンクリストをどのように逆転できますか？

まあ、私は、solutions in hereとhereのうちの1つが、リンクされたリストのループを検出することがそれを逆転することを見ました。 私の疑問は、リンク先リストの終わりがわからない場合、リンクされたリストを元に戻すことができる方法です。ループを持つリンクリストをどうやって逆転させることができますか？

Answer 1

まずは、この文脈では「逆転」とは何かを定義する必要があります。おそらく、何をする必要が

は、（1）それは巡回

（2）そのリンクを壊す可能リンクを見つけることである

（3）その後、何とかリストを逆転します。

効率的に行うことは、サイクルを識別する効率的な方法を見つけることを意味します。しかし、ノードが既に存在するかどうかを知るための操作をスタックに仮定すると、すでに見たノードへのリンクを与えるまで、ノードをスタックにプッシュするだけで済みます。その後、スタックをポップし、voilaあなたは逆の順序でリストを持っています。

は擬似コードでは、あなたはISIN操作

stack: 
    init() 
    push(node) 
    pop() returns node 
    isIn(node) returns Boolean 

でスタックを必要と

do 
    get next node 
    if node isIn stack 
    then 
     while stack not empty 
      pop node 
     break 
    else 
     push node in stack 
    fi 
od 

Answer 2

のようなものは、私はあなたがそれを持つリンクリストを逆にする意味を定義する必要が第一だと思いますループ。あなたは、リンクされたリストを持っていると仮定しましょう：

1->2->3->4->5-| 
    ^  | 
     |-------|     

ので、通常のリストを印刷するかどう：12345345345をあなたはサイクルのは、逆に、リンクされたリストは、すべての矢印はその方向を逆転させてきたし、逆にそれが必要意味するだろうと言ってみましょうトラバース続ければ

54354312は、今、あなたはこのような何かを行うことができます印刷：

prev=head; 
curr=head->next; 
while !curr->visited && curr->next!=end 
    tmp=prev 
    prev=curr 
    curr=curr->next 
    prev->next=tmp 
    curr->visited=True 

これは擬似コードで、ロジックで彼らのかもしれ小さな誤差はそれほどそのままコピーしませんが、それは1つの基本的な考え方です。