数据结构--逆序一个单链表

这个问题有两种解法。

第一种，我取名叫尾删头插法：

核心思路：将每一次oldhead后面的tmp节点删除，并将该节点头插，依次循环。直到oldhead变成链表的尾部，即tmp为空，循环结束。

如下图单链表：oldhead为逆序前原单链表的头，head为每逆置一次的单链表的新头，tmp为每一次要被删除的节点。过程1表尾删，过程2表示头插。

方法代码：

void SListReverse1(SListNode **pphead)
{
//这里我是通过二级指针**pphead来访问的头部，还可以通过将头部封装成一个结构体直接访问。
	SListNode *head = *pphead;//每次循环中始终指向当前链表的头
	SListNode *tmp = head->next;//每次循环中始终指向被删的节点
	SListNode *oldhead = *pphead;//每次循环中始终指向被删的前一个节点

	while (tmp)//tmp为空，代表逆序结束
	{
		oldhead->next = tmp->next;//架空tmp（后删）的一部分
		tmp->next = head;//让tmp变成新头（头插）
		head = tmp;//换头
		tmp = oldhead->next;//让tmp变成下一次循环中待删除的节点
	}
	*pphead = head;
}
           

第二种，我取名叫依次改指向法：

核心思路：找到原头部后面的每一个节点，依次让它指向每一次新的头部。

如下图：pre为每一次变换后链表的头部，cur为需要变换指向的节点，next为该节点等候一个节点，便于找到下一次需要变换的目标节点。

方法代码：

void SListReverse2(SListNode **pphead)
{
	SListNode *pre = *pphead;
	SListNode *cur= pre->next;//被执行操作的节点
	SListNode *next = cur;//被执行操作的后一个节点,暂时指在cur，在循环开始的时候跳转到其后一个节点

	pre->next = NULL;//此时的头，将会成为尾，所以要设置尾节点 
	while (next)
	{
		next = next->next;//放前面避免next为空。
		cur->next = pre;//改变箭头方向
		pre = cur;//循环节点依次后移
		cur = next;
	}
	*pphead = pre;//循环跳出时，cur和next都指向空，此时的头为pre
}
           

总结

1.不能忘记将新头赋给*pphead。

2.要注意两种方法结束循环时的判定条件。

最后再给出我的单链表的节点结构体定义：

typedef struct SListNode
{
	SLTDataType data;
	struct SListNode *next;
}SListNode;