单链表的逆转算法

单链表的逆转是一个很经典的算法，在考虑这样相对比较难点的算法时，最好的办法是把单链表的图画出来，这样对照着程序理解起来比较容易点，下面是用C++程序语言写的单链表逆转的算法，要求是在原有的单链表上进行逆转，不允许重新构造一个链表，算法如下所示：

template <class T>
void LinkList : :Inverse (Node<T> *&head)
	{
	if(head==NULL) return;
	Node *q=head,*p=head->next,*r=NULL;
	while (p!=NULL)
	{
	q->next=r;//逆转
	r=q;q=p;p=p->next;//指针前移
	}
	q->next=r;head=q;
}

①单链表初始状态如下图：

②算法执行第一次while后的图例，如下所示：

③单链表执行过程省略，最终逆转结果如下图：