单向链表反转

昨天遇到一个问题：如何遍历一次就反转一个单向链表。想了想也没什么好方法，用了很笨的一招，嘿嘿！将链表的各个节点得到并存在一个list中，然后倒序重组一下。感觉这个方法不是很好，不知道大家有什么好的方法，希望我这个破砖头能引出几块好玉来！

评论

8 楼 ray_linn 2009-02-16  

....放list里? 那还学个屁算法....

7 楼 yangyi 2009-02-16  

dandy 写道

yangyi 写道

需要三个指针吧

太抽象，具体点.

Pointer p = head,q,k;
p -> next = q;
q -> next = k;
do{
q->next = p;
p = q;
if(k is end){
   k->next = q;
}else{
  q = k;
  k = k->next;
}
}while(k is not end)

6 楼 dandy 2009-02-10  

抛出异常的爱 写道

a-> b -> c-> da-> null b->c->d->null        | x->aa->null  b->x  c->d->null     | y->ba->null  b->x  c ->y  d->null | z->ca->null  b->x  c->y   d->z

这样的话链表岂不是变成了：d→z→c→y→b→x→a ？

5 楼 抛出异常的爱 2009-02-09  

a-> b -> c-> d

a-> null b->c->d->null        | x->a
a->null  b->x  c->d->null     | y->b
a->null  b->x  c ->y  d->null | z->c
a->null  b->x  c->y   d->z

4 楼 dandy 2009-02-09  

yangyi 写道

需要三个指针吧

太抽象，具体点.

3 楼 dandy 2009-02-09  

myreligion 写道

反转就是一个个取出，然后放到Stack里面吧？呵呵。

可能用反转不太确切，比如链表是a→b→c→d，现在变成d→c→b→a，链表每个节点的前一个节点变为他的下一个节点。

2 楼 myreligion 2009-02-09  

反转就是一个个取出，然后放到Stack里面吧？呵呵。

1 楼 yangyi 2009-02-09  

需要三个指针吧