一、题目

设计一个算法，实现将头结点为head的单链表就地逆置，即利用原带头结点单链表head的结点空间将数据元素序列（a0,a1,…,an-1）逆置为（an-1,…, a1,a0）。

本题所使用的数据结构定义如下：

typedef  int  ElemType ;

单链表的数据结构定义：

typedef  struct  Lnode

{   ElemType  data;     /*  数据域，保存数据元素(结点的值)   */

struct   Lnode  *next;      /*  指针域  */

}LinkList;        /*  结点的类型   */

二、算法思路

1、若单链表为空表或单链表中只有一个元素，则无需进行逆置。

2、若单链表有两个或两个以上的元素，则定义指针p指向首元结点，定义指针q指向首元结点的下一个结点。

3、通过改变头指针、指针p、指针q所指的结点的指针域的指向来改变链表中的结点顺序，使q所指结点移动到首元结点的位置。

4、将指针p和指针q后移一位，重复进行操作3，直到遍历整个链表，即q指向空为止。此时得到的是就地逆置后的链表。

三、程序实现

void reverseList(LinkList*head) {
	if (head->next == NULL || head->next->next == NULL) {//判断单链表是否为空表或只有一个元素
		return;
	}
	LinkList* p = head->next;//定义指针p指向首元结点
	LinkList* q = p->next;//定义指针q指向首元结点的下一个结点
	while (q) {//若q不为空，则进入循环
		p->next = q->next;//使q所指结点移动到首元结点的位置
		q->next = head->next;
		head->next = q;
		q = p->next;//将指针p和指针q后移一位
	}
}