リンクされたリストを元に戻す方法は？

Question

Node reverse(Node head) { 
    Node previous = null; 
    Node current = head; 
    Node forward; 

    while (current != null) { 
     forward = current.next; 
     current.next = previous; 
     previous = current; 
     current = forward; 
    } 

    return previous; 
} 

リストをどのように逆転させるのですか？私は最初に2番目のノードをforwardに設定することになる。次に、current.nextがnullノードpreviousに等しいと言います。その後、previousはcurrentになりました。最後にcurrentはforwardになりますか？

私はこれを理解することができないとどのようにその逆転。誰かがこの作品の仕組みを説明できますか？

Answer 1

リストを反復的に逆転させ、[head、previous]の間隔のリストを正しく逆転させます（現在は正しく設定されていない最初のノードです）。

• あなたはあなたがあなたの場合は、正しい方向で、前を指しているために、現在のリンクを、設定すること
• から継続できるように、現在の次のノードを覚えている：あなたは次の操作を行い、各ステップで
それについて考える今現在もそのリンクが正しく
• 設定しているので、あなたはあなたは、そのリンクが第一歩

にremebered一つであることが正しく設定HAEない最初のノードを変更、現在のことは、以前の変更

これをすべてのノードに対して行うと、証明することができます（誘導など）。リストが正しく逆転されること。

Answer 2

コードは単にリストを歩き、リンクが前の尾に達するまでリンクを反転し、新しい髪として返します。後

Node 1 (Head) -> Node 2 -> Node 3 -> Node 4 (Tail) -> null 

：

null <- Node 1 (Tail) <- Node 2 <- Node 3 <- Node 4 (Head) 

Answer 3

Answer 4

public Node getLastNode() 
{ 
    if(next != null) 
     return next.getLastNode(); 
    else 
     return this; 
} 

public Node reverse(Node source) 
{ 
    Node reversed = source.getLastNode(); 
    Node cursor = source; 

    while(cursor != reversed) 
    { 
     reversed.addNodeAfter(cursor.getInfo()); 
     cursor = cursor.getNodeAfter(); 
    } 

    source = reversed; 
    return source; 
} 

Answer 5

私はそれを呼び出すを "チェリーピッキング" の前に

。この考えは、スワップの数を最小限に抑えることです。スワップはニア・インデックスとファー・インデックスの間で行われます。その2パスアルゴリズムです。

(Odd length) A -> B -> C -> D -> E 
    (Even length) A -> B -> C -> D 

    Pre-Condition: N >= 2 

    Pass 1: Count N, the number of elements 

    Pass 2: 
      for(j=0 -> j<= (N/2 -1)) 
      { 
       swap(j, (N-1)-j) 
      } 

例1：

For above Odd length list, N = 5 and there will be two swaps 

     when j=0, swap(0, 4) //post swap state: E B C D A 
     when j=1, swap(1, 3) //post swap state: E D C B A 


    The mid point for odd length lists remains intact. 

例2は：

For above Even length list, N = 4 and there will be two swaps 

     when j=0, swap(0, 3) //post swap state: D B C A 
     when j=1, swap(1, 2) //post swap state: D C B A 

• スワップは逃した任意の健全性チェックがあるかもしれません、だけではなく、ポインタにデータに適用されますしかし、あなたはその考えを持っています。

Answer 6

反復

current = head //point current pointer to head of the linked list 

while(current != NULL) 
{ 
forward = current->link; //point to the next node 
fforward = forward->link; //point the next node to next node 
fforward->link = forward;//1->2->3,,,,,,,,,this will point node 3 to node 2 
forward->link = current; //this will point node 2 to node 1 
if(current == head) 
current->link = NULL;// if current pointer is head pointer it should point to NULL while reversing 

current = current->link; //traversing the list 
} 
head = current; //make current pointer the head pointer 

Answer 7

list_t *reverse(list_t *a) 
    { 
    list_t *progress = NULL; 
    while(a) 
    { 
     list_t *b; //b is only a temporary variable (don't bother focusing on it) 
     b = a->next; 
     a->next = progress; //because a->next is assigned to another value, we must first save a->next to a different variable (to be able to use it later) 
     progress = a; //progress is initially NULL (so a->next = NULL (because it is the new last element in the list)) 
     a = b; //we set a to b (the value we saved earlier, what a->next was before it became NULL) 
     /* 
     now, at next iteration, progress will equal a, and a will equal b. 
     so, when I assign a->next = progress, I really say, b->next = a. 
     and so what we get is: b->a->NULL. 
     Maybe that gives you an idea of the picture? 
     What is important here is: 
      progress = a 
     and 
      a = b 
     Because that determines what a->next will equal: 
      c->b->a->0 
     a's next is set to 0 
     b's next is set to a 
     c's next is set to b 
     */ 
    } 
    return progress; 
    } 

Answer 8

基本的な考え方を用いて、単独でリンクされたリストを逆にすると、最初のリストからヘッドノードを切り離し、前記第二のリストの先頭にそれを取り付けることです。最初のリストが空になるまで繰り返してください。

擬似コード：

function reverseList(List X) RETURNS List 
    Y = null 
    WHILE X <> null 
     t = X.next 
     X.next = Y 
     Y = X 
     X = t 
    ENDWHILE 
    RETURN Y 
ENDfunction 

あなたは邪魔されずに元のリストを残したいなら、あなたはヘルパー関数を使用して再帰的にコピーバージョンをコーディングすることができます。

function reverseList(List X) RETURNS List 
    RETURN reverseListAux(X, null) 
ENDfunction 

function reverseListAux(List X, List Y) RETURNS List 
    IF X = null THEN 
     RETURN Y 
    ELSE 
     RETURN reverseListAux(X.next, makeNode(X.data, Y)) 
ENDfunction 

ヘルパー機能はテール再帰的です。これは、反復を使用してコピーの反転を作成できることを意味します。

function reverseList(List X) RETURNS List 
    Y = null 
    WHILE X <> null 
    Y = makeNode(x.data, Y) 
    X = X.next 
    ENDWHILE 
    RETURN Y 
ENDfunction