【背景】
单向链表由于其存储灵活，所有的元素位置是通过额外开辟的指针作为指向的，于是在复习过程中，不由得想象一下如何将链表进行反转。
参考网上的教程，大多是用改变指针的指向进行实现，当然也有利用递归栈的特殊性质进行实现，考虑到复习时间不足，本文对其中一种实现方法进行分析，并给出源码实现。
【源码运行环境】
操作系统：MAC OS X 10.13.4
编译环境：CLion (C++ 14) cmake
【分析】
现假定针对这样一个结构构成的链表进行分析：
首先，在上图基础上做辅助指针准备工作。
为了保存链表上下文（中间状态）
本文设置了四块指针：
-
head —> 保存链表头结点
-
cur —> 保存前驱节点（游标）
-
top —> 保存待反转节点（游标）
-
first —> 保存元素首节点
设置后的指针结构如下：
本文采用一种元素前插倒转法进行链表倒置。
算法描述如下：
-
将元素上下文用first首指针保存；
-
将链表头节点用head指针保存；
-
现阶段链表划分为两个子集s1(反转后状态),s2（未反转状态）；
-
其中cur是指向s1集合中的尾元素，top指向的是s2集合中的首元素；
-
将头结点(head-next)指向在s2集合中的首元素（top指向的元素）；
-
利用前驱指针cur-next指向s2集合中的次元素(top->next);
-
将s2集合中的首元素指向（top->next）first元素首部(first);
-
将top指针后移（top = cur->next）；
-
判断top指针是否为空；
-
case 1: top为空 结束反转
-
case2 : top不为空重复1-9步骤
算法数学描述：
起始:
s1 = {}
s2 ={S1,S2,S3,S4,…Sn}
第一次：
s1 = {S1}
s2 = {S2,S3,S3,S4,…,Sn}
第二次：
s1 = {S2,S1}
s3 = {S3,S4,S5}
…
第n次：
s1 = {Sn,…,S3,S2,S1}
s3 = {}
算法图解如下：
第一步步骤如下：
第一步完成时：各指针状态
简化后(第二次开始状态)：
第二次步骤：
简化后（第三次起始）指针上下文如下：
当top指向NULL节点时，此时循环结束，反转完成。
【算法源码实现】
核心代码如下：
Status LinkListReverse(Link *L)
{
if(LinkListEmpty(*L))
{
return OVERFLOW;
}
Link head = *L;
Link cur = head->next;
Link top = cur->next;
Link first = NULL;
while(top != NULL)
{
first = head->next;
head->next = top;
cur->next = top->next;
top->next = first;
top = cur->next;
}
return TRUE;
}
【总结】
本文介绍了一种实现单向链表反转的方法并给出了实现，但是反转的算法还有很多值得改善的地方，也有不同的算法可以实现同样的功能。（递归法、后插反转法等）。算法的学习道路还很深，希望自己能够借此机会锻炼自己的计算机思维能力。（共勉）。
【参考文献】
-
《大话数据结构》.程杰.清华大学出版社