单向链表的反转是一个经常被问到的一个面试题，也是一个非常基础的问题。比如一个链表是这样的： 1->2->3->4->5 通过反转后成为5->4->3->2->1。最容易想到的方法遍历一遍链表，利用一个辅助指针，存储遍历过程中当前指针指向的下一个元素，然后将当前节点元素的指针反转后，利用已经存储的指针往后面继续遍历。源代码如下：
struct linka {
int data
linka* next
}
void reverse(linka*&head)
{
if(head ==NULL)
return
linka*pre, *cur, *ne
pre=head
cur=head->next
while(cur)
{
ne = cur->next
cur->next = pre
pre = cur
cur = ne
}
head->next = NULL
head = pre
}
还有一种利用递归的方法。这种方法的基本思想是在反转当前节点之前先调用递归函数反转后续节点。源代码如下。不过这个方法有一个缺点，就是在反转后的最后一个结点会形成一个环，所以必须将函数的返回的节点的next域置为NULL。因为要改变head指针，所以我用了引用。算法的源代码如下：
linka* reverse(linka* p,linka*&head)
{
if(p == NULL || p->next == NULL)
{
head=p
return p
}
else
{
linka* tmp = reverse(p->next,head)
tmp->next = p
return p
}
}
栈先入后出，链表从投开始遍历；所以如栈然后再依次出栈就完成了逆置；现写的，没有测试，不过应该没问题：
#define int ElemType
typedef struct Node{
ElemType data
Node *next
}Node, *List
List reverseList(List head)
{
assert(head)
if (head->next == NULL) //如果链表长度为1，就不需要利用栈了
return head
stack<List>listS
//从头开始入栈
while (head != NULL)
{
listS.push(head)
head = head->next
}
//出栈
List pHead = listS.top()//保存头节点
List pre = NULL , cur = NULL //当前节点和前一个节点
while(listS.size())
{
//如果是第一个节点
if (pre == NULL){
pre = listS.top()
listS.pop()
}
//不是第一个节点
else{
cur = listS.top()
pre->next = cur
pre = cur
listS.top()
}
}
pre ->next = NULL //置尾结点的下一个节点为NULL；
return pHead
}
