0

反復アプローチを使用して二重にリンクされたリストを逆にしようとしていますが、元のリストのポインター スタイルの変更へのポインターを使用していなくても、元のリストが変更されている部分にぶつかります。

これは私が使用している逆関数でheadあり、メインのように宣言されたローカル変数でNode* head = NULL;あり、値のセットが既に入力されています。 

Node* reverse_iterative(Node* head)
{
    if(head == NULL || head->next == NULL)
        return head;

    Node *prev, *current=head, *temp;
    while(current != NULL)
    {
        current->prev = current->next;
        current->next = temp;
        temp = current;
        current = current->prev;
    }
    return temp;
}

これは私がメインでこれをどのように使用したかです:

Node* rev = NULL;
rev = reverse_iterative(head);

ここに私が得た出力があります:

original list: 15 <=>25 <=>35 <=>45 <=>55 <=>65 <=>75 <=>
making the list actually reverse: 75 <=>65 <=>55 <=>45 <=>35 <=>25 <=>15 <=>
after reversing, the original list now: 15 <=>

元のヘッド ノードが変更されていた部分を取得できませんでした。

4

2 に答える 2

3

while ループを注意深く見て、ループの最初の反復で次のステートメントを検討してください。

current->next = temp;

tempこの割り当ての時点で何が入っていますか? さらに多くのコードを公開すると、次のようになります。

Node *prev, *current=head, *temp;
while(current != NULL)
{
    current->prev = current->next;
    current->next = temp;
    temp = current;
    current = current->prev;
}

temp は初期化されていないため、未定義のポインター値であることに注意してください。元の head-ptrの次のptr は、初期化されていない一時に保持されているガベージにリセットされています。

次の手順を実行して、これを修正します。

Node *current=head, *temp=NULL;
while(current != NULL)
{
    temp = current->prev;
    current->prev = current->next;
    current->next = temp;
    temp = current;
    current = current->prev;
}

私はそれをテストする機会がありませんでしたが、それはあなたが探しているものに近づくはずです.

于 2012-10-29T19:37:55.353 に答える
3

私の理解が正しければ、元のリストをまったく変更されたくないでしょう。

しかし、ループは元の要素を変更します。たとえば、current は最初に head 要素を指し、次にその next および prev を変更します。これは、元の head 要素が変更されたことを意味します。

于 2012-10-29T19:49:10.850 に答える