数据结构(单链表的逆置)

注意事项：逆置后，一定要将头结点指向首元结点，修改尾结点的指向，并且将尾结点的next域置为空，可以通过逆置后再进行尾插测试结果是否正确。

方法一：

算法思想:

从原链表的首元结点开始，依次遍历，将后一节点指向前一个节点，直至原链表的节点为空。

代码实现:

template <class ElemType>
	void LinkList<ElemType>::Inverse()
	{
		LinkNode<ElemType> *p,*q,*s;
		p=head->next;
		q=p->next;
		while(q)
		{
			s=q->next;
			q->next=p;
			p=q;
			q=s;
		}
		tail=head->next;
		head->next->next=NULL;
		head->next=p;
	}

方法二：

算法思想:

首先让原链表的尾节点指向首元结点，将各个节点依次紧贴尾结点的后面进行尾插，直至执行到原链表尾结点的前一个节点。

代码实现：

template <class ElemType>
	void LinkList<ElemType>::Inverse()
	{
		int i=1;
		LinkNode<ElemType> *p,*q;
		p=head->next;
		while(i<len)
		{
			q=p->next;
			p->next=tail->next;
			tail->next=p;
			p=q;
			i++;
		}
		tail=head->next;
		head->next=q;
		tail->next=NULL;
	}

方法三：

算法思想:首先让链表首元节点初始为空，表中节点从原链表中依次“删除”，再逐个插入链表的表头（即“头插”到逆置链表中），使它成为逆置链表的“新”的第一个结点，直至原链表为空。

代码实现：

template <class ElemType>
	void LinkList<ElemType>::Inverse()
	{
		LinkNode<ElemType> *p=head->next,*q;
		tail=head->next;
		head->next=NULL;
		while(p)
		{
			q=p;
			p=p->next;
			q->next=head->next;
			head->next=q;
		}
	}