反转链表 用递归算法 讲解一下吧 我实在是理解不了链表反转的问题了
最重要的是表明 那个指针指向那里？指针的指向问题始终解决不了啊
拜托各位大虾了，反转链表的问题烦恼我很久了，解决不了啊
小女子，真的谢谢你们了
[解决办法]
// 链表结构
struct List { struct List* nextl int key; };
// 递归实现反转链表
List *reverse(List *oldList, List *newHead=NULL)
{
// 记录剩余的链表
List *next = oldList-> next;
// 将当前的节点插入到newHead链表的开头
oldList-> next = newHead;
newHead = oldList;
// 递归处理剩余的链表
return (next==NULL)? newHead: reverse(t, newHead);
}
void main()
{
List *list;
// 调用的时候newHead使用默认的NULL
List *q = reverse(list);
}
[解决办法]
你有3个问题都没有弄清楚之前不适合做这个题目：
1. 指针的概念，到底什么时候是使用的指针本身，什么时候是引用的所指向的值。
2. 递归的实现，你需要找一个简单的递归函数先研究研究，刚开始研究递归的时候确实有点难度，不过弄明白就好了。建议弄递归之前先复习一下计算机如何执行代码的，也就是栈在程序执行时候起到的作用。
3. 链表本身的数据结构，先不要去管什么双向链表，什么树啊图的，找一个简单的单项链表，看看是如何进行插入删除操作的。自己写点代码测试测试，体会体会。
上面3个问题一个个解决，估计1个礼拜就够了，然后你就会恍然大悟，原来是这样。。。
[解决办法]
单链表的逆置的实现:
(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
[解决办法]
head-> next-> next=p,的地方看不明白，不知道到底指的是哪里，
====================================
head-> next 是 head 的下一个节点
-> next 表示再下一个节点
也就是 head 后第二个节点，=p 表示赋值为p
就是把 p 作为 head 后第二个节点
p=head 与head=p
＝＝＝＝＝＝＝＝＝＝＝
p=head //p 指向 head指向的位置
head=p //head指向 p指向的位置
假设 p=&a, head=&b
p=head, 那么 p和head 都 指向b
head=p, 那么 p和head 都 指向a
