如何实现一个单链表的反转?

FH

用栈可以实现

另：一个指针的算法
12340

21340
23140
23410

32410
34210

43210

converse

原帖由 "FH" 发表：
用栈可以实现

另：一个指针的算法
12340

21340
23140
23410

32410
34210

43210

时间复杂度大了一些，不能一次遍历链表就完成逆转，当然啦由于只用了一个指针可以减少空间的消耗，具体用哪一个还要具体问题具体分析了。

aero

原帖由 "FH" 发表：
用栈可以实现

另：一个指针的算法
12340

21340
23140
23410

32410
34210

43210

没看懂。

converse

>;>;用栈可以实现
我觉得这样的话有点偷换概念了，就好像《九品芝麻官》里面豹子头去嫖妓的时候说；“我玩完了她不给钱就不算卖了”。

言归正传，我还是认为不用任何“辅助结点”的话是不可能完成要求的，使用栈其实也是变相的使用了辅助结点，你说呢？

converse

>;>;没看懂。
其实和冒泡排序的原理很像，就是一个个的移动结点到相应的位置，移动完一个再移动下一个，直到逆转完成。

FH

我觉得不能算偷换概念。
依我的理解，老师就是不想让学生用倒腾指针的方式实现。

converse

>;>;依我的理解，老师就是不想让学生用倒腾指针的方式实现。
也许老师是想考察学生对栈的理解吧，就我而言，一开始想到的就是怎么操作指针－－这是从语言角度想到的，如果能想到从栈操作的角度去解决就是从数据结构和算法的角度去考虑的，这样说来，这个题目是个不错的题目。这个问题讨论到这里应该差不多了。

assiss

不是吧?
这个问题是为了考查学生对栈的理解?
这这这....这个推论,....也太......什么了吧......

自由星辰

栈也算是辅助节点吧

自由星辰

这样行吗？

struct student *reverse(head)
struct student *head;
{
  struct student *p0,*p1,*p2;
  if(head==NULL||head->;next==NULL)return(head);
  p0=head;
  p1=p0->;next;
  p2=p1->;next;
  for(;p2!=NULL
    {
      p1->;next=p0;
      p0=p1;
      p1=p2;
      p2=p2->;next;
    }
  p1->;next=p0;
  head->;next=NULL;
  head=p1;
  return(head);
}