问题
思路
cur = pre->next; post = cur=>next; cur->next = pre; cur = post;
代码
void reverseLink(Node *root) { if(root->next->next) //如果只有一个结点，那就没有必要逆转了 { Node *target = root->next; //设好靶子，目的是最后一个结点指向为空！ Node *pre = root->next; Node *cur = pre->next; Node *post = NULL; while(cur) { post = cur->next; cur->next = pre; pre = cur; cur = post; if(post) post = post->next; } root->next = pre; target->next = NULL; } }
完整执行
#include <iostream> using namespace std; typedef struct node { int data; struct node *next; }Node; void createLink(Node *root) { Node *n1 = new(Node); n1->data = 1; n1->next = NULL; root->next = n1; Node *n2 = new(Node); n2->data = 2; n2->next = NULL; n1->next = n2; Node *n3 = new(Node); n3->data = 3; n3->next = NULL; n2->next = n3; } void traverseLink(Node *root) { Node *cur = root->next; while(cur) { cout << cur->data << endl; cur = cur->next; } } void reverseLink(Node *root) { if(root->next->next) { Node *target = root->next; Node *pre = root->next; Node *cur = pre->next; Node *post = NULL; while(cur) { post = cur->next; cur->next = pre; pre = cur; cur = post; if(post) post = post->next; } root->next = pre; target->next = NULL; } } void deleteLink(Node *root) { Node *cur = root, *post = NULL; while(cur) { post = cur->next; delete(cur); cur = post; } } int main() { Node *root = new(Node); root->next = NULL; createLink(root); cout << "Pre reverse:" << endl; traverseLink(root); reverseLink(root); cout << "After reverse:" << endl; traverseLink(root); deleteLink(root); }
结果