设计一算法，将已建立的单链表进行逆置

     单链表逆序有很多种方法，可是好多种方法都是逆序后就不能再使用之前定义的函数了，因为你的头结点变动了，不再是之前所定义的first或是head了，所以之前的方法都要重写，后来我终于想到了种很好的方法了。

    为了不重开空间，我们可以就在原来的那个单链表上做。如下图：

依次这样下去，直到p=NULL时，再把头指针赋值给prev即可。

也就是说我们循环的条件是while(p!=NULL)。即：

void LinkList<DataType>::Rever()
{
Node<int> *prev = NULL;//定义空指针
Node<int> *next;//定义P指针的下一个指针
Node<int> *p = first->next;//保留头指针
while(p!=NULL)
{
next = p->next;
p->next = prev;
        prev = p;
p = next;
}
first->next = prev;

}

此为逆序函数。

完整的示例代码如下：

#include<iostream.h>
template<class DataType>
class Node{ 
  public:     
 DataType data;  
 Node<DataType> *next;
};


template<class DataType>
class LinkList
{
public:
LinkList(DataType a[],int n);
DataType Get(int i);
int Locate(DataType x);
void Insert(int i,DataType x);
DataType Delete(int i);
int Length();
void PrintList();
void Rever();
private:
Node<DataType> *first;

};
//有参构造
template<class DataType>
LinkList<DataType>::LinkList(DataType a[],int n)
{
first = new Node<int>;first->next=NULL;
for(int i=0;i<n;i++)
{
Node<int> *s=new Node<int>;s->data=a[i];
s->next=first->next;first->next=s;
}
}
//遍历功能
template<class DataType>
void LinkList<DataType>::PrintList()
{
Node<int> *p = first->next;
while(p!=NULL)
{
cout<<p->data<<" ";
p=p->next;
}
if(p==NULL)
{cout<<endl;}
}
//插入功能
template<class DataType>
void LinkList<DataType>::Insert(int i,DataType x)
{
Node<int> *p=first; 
int count=0;
while(p!=NULL&&count<i-1)
{
p=p->next;
count++;
}
if(p==NULL)throw"位置";
else{
Node<int> *s=new Node<int>;s->data=x;
s->next=p->next;p->next=s;
}
}
//删除功能
template<class DataType>
DataType LinkList<DataType>::Delete(int i)
{
Node<int> *p=first;
Node<int> *q;
int count=0;
while(p!=NULL&&count<i-1)
{
p=p->next;
count++;
}
if(p==NULL||p->next==NULL)
throw"位置";
else{
q=p->next;
int x=q->data;
p->next=q->next;
delete q;
return x;
}
}
//按位查找
template<class DataType>
DataType LinkList<DataType>::Get(int i)
{
Node<int> *p=first->next;
int count=1;
while(p!=NULL&&count<i)
{
p=p->next;
count++;
}
if(p==NULL)throw"位置";
else return p->data;
}
//长度
template<class DataType>
int LinkList<DataType>::Length()
{
Node<int> *p=first->next;
int count = 0;
while(p!=NULL)
{
p = p->next;
count++;
}
return count;
}


//逆值
template<class DataType>
void LinkList<DataType>::Rever()
{
Node<int> *prev = NULL;
Node<int> *next;
Node<int> *p = first->next;
while(p!=NULL)
{
next = p->next;
p->next = prev;
   prev = p;
p = next;
}
first->next = prev;

}


void main()
{
int a[10] = {0,1,2,3,4,5,6,7,8,9};
int n = 10;
LinkList<int> list(a,n);
cout<<list.Length()<<endl;
list.PrintList();
//插入
list.Insert(3,4);
list.PrintList();
//删除
list.Delete(3);
list.PrintList();
//查找
cout<<list.Get(3)<<endl;
//逆序
list.Rever();
list.PrintList();
}