反向双向链表

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中，当我打开它时，它会打印出所有的值，然后挂起（在闪烁的光标处），不执行任何操作。

解决方案：明白了。这是我的功能最终成为。

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

那不是你的意思是做 - 它会导致您重复循环遍历节点1和零，而不是进展到节点2和更远......

请注意，你可以，如果你把这个代码到反向环路都容易调试这样的：

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

等等并不需要很长时间打字，揭示了所有:)

（可能你会剪下来做100 3代替）

我只是做手工为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. 
}