Обратный двойной список

Question

Вот моя простая программа со связанными списками, которая создает дважды связанный список, и он работает.

#include <iostream> 
using namespace std; 

typedef struct node { 
    int data; 
    node *next; 
    node *prev; 
}node; 

void printList(node *temp); 

int main() 
{ 
    node *head; 
    head = new node; 
    head->prev = NULL; 
    node *next = head; 
    node *prev = head; 
    node *temp = head; 
    node *current = head; 

    //creates 100 nodes, last one points to next 
    for(int x = 0; x<100; x++) 
    { 
    temp->data = x; 
    current = temp; 
    temp = new node; 
    current->next = temp; 
    temp->prev = current; 
    temp->next = NULL; 
    } 
    //========================================= 

    printList(head); 

    //=========== set everything to head =========== 
    current = head; 
    prev = head; 

    //============= reverses linked list ============ 
    while(current->next != NULL) 
    { 
    next = current->next; //moves next pointer to next node 
    current->prev = next; //points current's previous to next node 
    current = next;   //set current pointer to next node 
    current->next = prev; //set current's next to previous node 
    prev = current;   //move prev node up to current 
    } 
    //================================================ 

    printList(head); 
    cout<<"done"; 

    return 0; 
}  

void printList(node *temp) 
{ 
    while(temp->next != NULL) 
    { 
     cout<<temp->data<<'\n'; 
     temp = temp->next; 
    } 
} 

После того, как я добавлю обратную функцию, она висит. Собственно, сама функция работает, но в среде IDE, когда я LOOP это, она печатает все значения, а затем просто зависает (сидит там с мигающим курсором) и ничего не делает.

Решение: Получил его на работу. Это то, чем моя функция оказалась.

current = head;   //set current pointer to head 
prev = head;   //set previous pointer to head 


next = current->next; //moves next pointer to next node 
current->next = NULL; //set the next of the header to NULL, because it will actually be the last 
         //node of reversed list. 
current->prev = next; //set previous of the header to the next node. 

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

Answer 1

Ваш обратный алгоритм в основном сломан.

На первом проходе через:

current = head; // Current is pointing at node 0, node0->next is 1 from before 
prev = head; // Prev is pointing at node 0 

next = current->next; // next is pointing at 1 
current->prev = next; // node0->prev is pointing at 1 
current = next;  // current is pointing at 1 
current->next = prev // node1->next is pointing at 0 

затем следующий проход

next = current->next // read up there ^^^ node1->next is pointing at 0 

... поэтому следующий восходит к к узлу 0.

Это не то, что вы хотели do - это заставляет вас циклически обходить узлы 1 и ноль повторно, вместо перехода на узел 2 и далее ...

Обратите внимание, что вы могли бы легко отлаживается, если вы поместите этот код в обратном цикле:

cout<<"\nStarting iteration" 
cout<<"\nNext is at" << next->data 
cout<<"\nCurrent is at" << current->data 
cout<<"\nCurrent->next is" << current->next->data 

и т.д ... не занимает много времени, чтобы набрать, показывает все :)

(вероятно, вы бы сократить его, чтобы сделать 3 вместо 100)

Я просто сделал шаги для 3-х узлов вручную (на бумаге), чтобы вывести этот ответ ...

Answer 2

Посмотрите это простое решение ..

Node* Reverse(Node* head) 
{ 
Node * curr=head; 
Node * prev=NULL,* nxt=NULL; 

while(curr!=NULL) 
    { 
    nxt=curr->next; 

    curr->next=prev; 
    curr->prev=nxt; 

    prev=curr; 
    curr=nxt; 
    } 

return prev; 
// Complete this function 
// Do not write the main method. 
}