23

検討：

 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.nextis equal to a nullnodeと表示されますprevious。次に、previousis nowと表示されcurrentます。最後currentはforward？

これと、それがどのように逆転しているのか理解できないようです。誰かがこれがどのように機能するか説明してもらえますか?

4

12 に答える 12

45

ここに画像の説明を入力

于 2012-02-01T07:30:18.760 に答える
4

リストを繰り返し反転し、常に間隔 [head, previous] のリストを正しく反転させます (つまり、current は、リンクが正しく設定されていない最初のノードです)。各ステップで、次のことを行います。

  • 現在の次のノードを覚えているので、そこから続行できます
  • 現在のリンクが前を指すように設定します。これは、考えてみれば正しい方向です。
  • 現在のリンクも正しく設定されているため、以前を現在の状態に変更します。
  • リンクが正しく設定されていない最初のノードを、最初のステップで記憶されたノードに変更します。

すべてのノードに対してこれを行うと、リストが正しく反転されることを (たとえば帰納法で) 証明できます。

于 2012-01-31T09:13:56.400 に答える
4

コードは単純にリストをたどり、前の末尾に到達するまでリンクを反転させます。これが新しい先頭として返されます。

前：

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

後：

   null <- Node 1 (Tail) <- Node 2 <- Node 3 <- Node 4 (Head)
于 2012-01-31T09:17:31.123 に答える
2

私はそれを「チェリーピッキング」と呼んでいます。アイデアは、スワップの数を最小限に抑えることです。近いインデックスと遠いインデックスの間でスワッピングが発生します。これは twp-pass アルゴリズムです。

    (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
  • スワッピングはデータのみに適用され、ポインターには適用されません。
于 2013-07-25T14:45:43.080 に答える
2 
  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 the 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;
  }
于 2015-09-23T04:07:15.837 に答える
1

反復を使用して片方向リストを逆にする:

current = head // Point the current pointer to the 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 the current pointer is the head pointer it should point to NULL while reversing

    current = current->link; // Traversing the list
}
head = current; // Make the current pointer the head pointer
于 2014-02-25T06:31:46.250 に答える
1

片方向リスト反転関数の実装:

struct Node
{
    int data;
    struct Node* link;
}

Node* head = NULL;

void reverseList()
{
    Node* previous, *current, *next;
    previous = NULL;
    current = head;

    while(current != NULL)
    {
        next = current-> link;
        current->link = previous;
        previous = current;
        current = next;
    }

    head = previous;
}
于 2019-03-04T19:07:59.847 に答える