上一篇，我们介绍了如何反转不带头节点的链表，这一篇，我们来写带头节点的链表

本篇我们采用原地反转法（不会新创建链表，空间复杂度为O(1)）

进入分析：

初始大概就是这样的，head什么都没有，只记录了下一个节点的地址

我们该怎们样让它反转呢？

首先确认要反转的对象，我们这里需要将a1和a2进行反转。

那么我们就需要设置一个begin和一个end ,来记录地址。

接下来，如图：

我们总共分为4步来完成我们的链表反转
第一步呢，我们利用end来获取end的下一个节点的地址，然后将a1直接指向这个节点。
第二步，我们将a2与end->next断开链接。
第三步，我们将a2的next变为a1。
第四步，将头节点的next改变为a2.
下来我们通过代码，来完成这个过程

void reversal(STnode* phead)
{
	STnode* begin = phead->next;
	STnode* end = phead->next->next;
	STnode* temp = end->next;
	begin->next = temp;
	end->next = phead->next;
	phead->next = end;
}

结果：

完美！！现在我们只需要循环起来就好了，那么我们的循环结束条件是什么呢？

我们在最开始的时候end 就代表的尾节点，所以当我们的end!=NULL时循环继续

void reversal(STnode* phead)
{
	STnode* begin = phead->next;
	STnode* end = phead->next->next;
	while (end != NULL) {
		STnode* temp = end->next;
		begin->next = temp;
		end->next = phead->next;
		phead->next = end;
		end = begin->next;
	}
}

这样就好啦！！
测试一下！

完美！！