链表反转的两种实现方法

对于链表的讨论似乎永远都不会过时。虽然现在有了容器，但是一味的使用它们，也使自己失去了锻炼的机会。前不久被导师问及链表反转的问题，结果编码、调 试，费了好大功夫才算完成了。而且，代码还没得到优化，完善。想不到许久没碰指针，对指针的操作竟生疏了不少。看来对技术的学习，真的不能放松啊～！

把代码简单整理下，大家参考：

#include using namespace std; //元结点 struct Node { int data; Node *next; }; //链表反转（循环方法） Node *Reverse(Node *head) { Node *prev = NULL; Node *cur = NULL; Node *next = head; for (; next != NULL; ) { cur = next; next = cur->next; cur->next = prev; prev = cur; } return prev; } //链表反转（递归方法） Node *Reverse2(Node *head) { if (!head) { return NULL; } Node *temp = Reverse2(head->next); if (!temp) { return head; } head->next->next = head; head->next = NULL; return temp; } //创建链表 Node *Construct(int *const array, int len) { Node *pre = NULL, *head = NULL; for (int i = len; i > 0; i--) { if (!pre) { head = new Node; head->data = array[len - i]; head->next = NULL; pre = head; } else { pre->next = new Node; pre = pre->next; pre->data = array[len - i]; pre->next = NULL; } } return head; } //销毁链表 void Destruct(Node *head) { Node *cur = head, *temp = NULL; while (cur) { temp = cur; cur = cur->next; delete temp; } } //打印链表 void Print(Node *head) { Node *cur = head; for (; cur != NULL; cur = cur->next) { cout << "data: " <<>data << endl; } } int main(int argc, char* argv[]) { Node *head = NULL; int array[] = {1, 3, 5, 7, 9, 10, 8, 6, 4, 2}; cout << endl << "Construct!" << endl << endl; head = Construct(array, 10); Print(head); cout << endl << "Reverse!" << endl << endl; head = Reverse(head); Print(head); cout << endl << "Reverse2!" << endl << endl; head = Reverse2(head); Print(head); cout << endl << "Destruct!" << endl << endl; Destruct(head); head = NULL; Print(head); return 0; }