Question

写出在链式存储结构下将线性表逆转的算法，要求使用最少的附加空间

Answer 1

假设是单链表存贮，从头遍历到尾，遍历每个元素是将指针反转，只需要一个额外空间。

算法描述：
header : 指向链表头

p=header;
pre=NULL;
next=NULL;
while(p!=NULL)
{
next=p->next;
p->next=pre;
pre=p;
p=next;
}
head=p;

这样就反转了。用了两个额外空间,时间复杂度O(n).

Answer 2

双链表就简单啦，把每个结点向前和向后两个指针交换一下就是了

Answer 3

引用zhoujin1012的回答：
假设是单链表存贮，从头遍历到尾，遍历每个元素是将指针反转，只需要一个额外空间。

算法描述：
header : 指向链表头

p=header;
pre=NULL;
next=NULL;
while(p!=NULL)
{
next=p->next;
p->next=pre;
pre=p;
p=next;
}
head=p;

这样就反转了。用了两个额外空间,时间复杂度O(n).

最后应该是head=pre