函数如何倒置倒置

数据结构有顺序存储和链存储两种存储方法。顺序存储的数组可以使用下标随机访问，但插入操作很麻烦，需要整个内存块，数组大小必须事先确定，缺乏灵活性。

链式存储动态分配节点，不需要整块的内存空间，插入和删除节点元素的操作比较方便。STL支持的list兼有顺序存储和链式存储的优点。自定义链式存储的链表需要自定义创建、插入、查询、删除、清除等函数，虽然有list可用，但自定义链表可以帮助我们从底层了解链式存储的实现方式。

链表的创建、遍历、查询、插入、删除操作请见前面的文章。

1 链表的倒置操作

除了头节点head指针以外，还需另外添加两个指针：cp和prev。三个节点指针在移动后各自的指向节点有一个不变的顺序：prev、cp、head（移动时，前面的一个指针可以与后面的并排并不能超过）。也就是head后移（移动至后驱节点，方向是→）后，在←方向还有cp、prev可以访问到，并通过cp.next = prev，构成←方向的链接指向：

全部操作动画演示：

2 代码

3 附代码

void Reverse(node * &head)
{
node * prev = NULL; //前一个节点
node * cp; //当前操作节点
while(head!=NULL)
{
cp=head;
head=head->next; //head后移
cp->next = prev;
//cp->next(相当于head后移前的head->nex)前指
prev=cp; //prev后移
}
head = prev;
}

－End－