解释一下 反转链表 的这个程序吧
只要解释算法部分，详细点吧，谢谢了，麻烦大家了
#include <iostream>
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: " < < cur-> 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;
}
[解决办法]
这个程序比较正规.是Robert Sedgewick书中的:
#include <iostream.h>
#include <stdlib.h>
struct node
{ int item; node* next;
node(int x, node* t)
{ item = x; next = t; }
};
typedef node *link;
int main(int argc, char *argv[])
{ int i, N = atoi(argv[1]), M = atoi(argv[2]);
link t = new node(1, 0); t-> next = t;
link x = t;
for (i = 2; i <= N; i++)
x = (x-> next = new node(i, t));
while (x != x-> next)
{
for (i = 1; i < M; i++) x = x-> next;
x-> next = x-> next-> next;
}
cout < < x-> item < < endl;
}
-----
link reverse(link x)
{ link t, y = x, r = 0;
while (y != 0)
{ t = y-> next; y-> next = r; r = y; y = t; }
return r;
}
[解决办法]
给你分析下两个反转函数：
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;
}
该函数先记入三个节点：cur为当前节点， next为当前节点的下一个节点，prev 为当前节点的前一个节点，函数通过循环把cur-> next 指向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;
}
函数通过递归head-> next-> next = head就是把一个节点的下一节点的尾指针指向自己。
[解决办法]
(1)循环方法 算法
struct link
{
int data;
struct link *next;
};
link reverse(link x)
{
if( NULL==x )
return NULL;
link t=NULL;
link r=NULL, y=x; //(0)
while(y!=NULL)
{
t = y-> next; //(1)
y-> next = r; //(2)
r = y; //(3)
y = t; //(4)
}
return r; //返回逆置后的链表
}
(二)原理
(0)(1)(2)(3)(4)分别对应以上程序的各序号
第一次while循环
-------------------------------------------
(0) r=NULL, y=x
r=NULL a ---> b ---> c ---> d --> NULL
|(0)
y
-------------------------------------------
(1) t =y-> next
r=NULL a ---> b ---> c ---> d --> NULL
|(0) | (1)
y t
--------------------------------------------
(2) y-> next = r
a ---> NULL b ---> c ---> d --> NULL
|(0) (2) | | (1)
y r t
---------------------------------------------
(3) r = y
a ---> NULL b ---> c ---> d --> NULL
|(0) (2) | (1)
y t
|(3)
r
---------------------------------------------
(4) y = t
a ---> NULL b ---> c ---> d --> NULL
|(0) (2) | (1)
| t
|(3) | (4)
r y
第二次while循环(并对上面进行整理)
---------------------------------------------
(1) t = y-> next
a ---> NULL b ---> c ---> d --> NULL
| | |(1)
r y t
---------------------------------------------
(2) y-> next = r
b ---> a ---> NULL c ---> d --> NULL
| (2) | |(1)
y r t
---------------------------------------------
(3) r = y
b ---> a ---> NULL c ---> d --> NULL
| (2) |(1)
y t
| (3)
r
---------------------------------------------
(4) y = t
b ---> a ---> NULL c ---> d --> NULL
| (2) |(1)
| t
| (3) |(4)
r y
第三个循环 (并对上面的进行整理)
---------------------------------------------
(1) t = y-> next
b ---> a ---> NULL c ---> d --> NULL
| | |(1)
r y t
以后的与第二次循环同, 最终可得:
d ---> c ---> b ---> a ---> NULL
引用地址：http://blog.programfan.com/trackback.asp?id=11456
[解决办法]
至于递归方法，基本思想是在反转当前节点之前先调用递归函数反转后续节点。
就是节点 n，
先反转后面的所有节点，
然后把 n 节点连接在逆置链表的尾部，完成反转。
即如下：
反转 head
＝＝》先反转head后面的所有节点（这里就是递归调用Reverse2(head-> next);）
反转好了之后把head连接在尾部，然后next指向NULL，完成
[解决办法]
head-> next-> next = head; //改为 n-> next-> next = n;
head-> next = NULL; //改为 n-> next = NULL;
可能就是这两个语句不怎么理解吧？
首先， head【注意，这个函数中的head不是链表的head，应该把函数中head理解一般化，把它理解为链表中的第 n 个节点，Node *Reverse2(Node *head) 也许改成Node *Reverse2(Node *n)比较不容易误解】
根据递归的思想，
先递归 Node *temp = Reverse2(n-> next); 完成后面节点的逆转，
这个时候，注意 只是逆转了 n 后面的节点，
n以及n以前的节点都没有变化， 所以， n-> next 指向的是它原来的后续节点，
【该节点根据逆转原理，位于逆转的链表尾部】
因此 n-> next-> next = n; 就是使得 n 的原后续节点的next指向为 n， 也就是将n放到了逆转的链表的尾部，然后n-> next = NULL; 将next置空。
如此递归，
就完成了链表的逆转。
