首先给出单向链表的结构
遍历一次链表，对于每一个节点p，记录p的前驱pre，将p节点的后继（即next域）指向pre，即可完成倒转。
1、设p节点指向头指针l的下一个节点（即指向第一个元素），pre设为NULL
2、若p的下一个节点为空，跳到4，否则跳到3
3、将q指向p的下一个节点，将p的next域指向pre节点，将pre指向p节点，将p指向q节点，跳到2
4、将p的next域指向pre节点
5、结束
显然，这道题目如果通过记录data域来实现调转，算法复杂度在O(n^2)级，因为在不使用辅助数组的情况下，每次颠倒需要从头节点以O(n)的时间复杂度找到需要颠倒的节点。所以我们不妨换一个想法，从链表的next域下手。很容易想到，如果我们将每个节点的next域都指向它的前驱而不是后继，就可实现调转。我们不妨具体举例说明。
假设前两个节点已经完成倒转，那么链表就可以表示成:
可以看出，链表变为了两部分。这时我们需要一个指针记录3的当前后继（也就是4），以完成后续遍历，之后将3的next域指向2，并记录3的位置（以便4指向3），即可完成前3个节点的倒转。
扣着的是头节点（头子）
车是首节点（首子）
马是次节点（次子）
牙签细的是指针指向，香头发黑的是指向，铁头细的是指向。
根据步骤写程序的伪算法（3步4循环，7张图片搞定），如下：
以下是while循环（条件：香头指向不为空）
第一个循环把马弄到车前面，
第二个循环把相弄到马前面
第三个循环把士弄到相前面
........
直到香指向为空后停止循环。
代码如下：只需要一个首结点pHead,就能把链表找到，并倒置。具体代码如下
p香=pHead->pNext
p铁=p香->pNext
p香->pNext=NULL
P香=p铁
while(p香 ！=NULL)
{
p铁=p香->pNext
p香->pNext=pHead->pNext
pHead->pNext=p香；
p香=p铁；
}
对照伪算法（三步四循环），和上面的代码是一一对应的：
第一步：香头指向首子，铁头指向次子
第二步：删掉首子指向次子（铁头所指向的那个子）的牙签
第三步：香头跟着铁头
以下循环条件：（条件：香头指向不为空）
{
循环1：铁头移动到香头的下一个指向
循环2：香头的下一个指向首子
循环3：头子的下一个跟着香头
循环4：香头跟着铁头
}
自己用道具操作几遍，然后把流程背会，以后自己根据流程写代码即可。
链表反转单向链表的反转是一个经常被问到的一个面试题，也是一个非常基础的问题。比如一个链表是这样的： 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
}
}
