Write a procedure to reverse a singly linked list in O(N) time using constant extra space.
一道数据结构的题，一点头绪也没耶，各位大虾帮帮忙哈，谢谢啦……很急耶

翻译过来应该是:编写一个程序将一个单链表就地逆置,要求时间复杂度为O(n).

void revers(point head)//链表逆转置
{ point p,q,r;
p=head->next;
q=head->next;
r=q->next;
if(p==NULL || q==NULL)
printf("该链表无须转置。");
p->next=NULL; p=q;
while(r->next)
{
q=r; r=r->next;
q->next=p; p=q;
}
r->next=p; head->next=r;
}

[此贴子已经被作者于2006-9-22 13:02:29编辑过]

OK,完成

如果是要交作业, 抄完之后  还是要多思考一下,弄明白的好

同求此题
偶然搜索到。。。看了一下觉得上面写的程序要用的时间是O（N^2)次吧——

不好意思，的确有问题。那个是空间复杂度为O（n）的。
现在改OK了，不过只给了个逆置函数，不是完整的原代码。
将链表建好后就可以用这个函数逆置。

[此贴子已经被作者于2006-9-22 13:05:12编辑过]