【背景】

单向链表由于其存储灵活，所有的元素位置是通过额外开辟的指针作为指向的，于是在复习过程中，不由得想象一下如何将链表进行反转。

参考网上的教程，大多是用改变指针的指向进行实现，当然也有利用递归栈的特殊性质进行实现，考虑到复习时间不足，本文对其中一种实现方法进行分析，并给出源码实现。

【源码运行环境】

操作系统：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;

}

【总结】

本文介绍了一种实现单向链表反转的方法并给出了实现，但是反转的算法还有很多值得改善的地方，也有不同的算法可以实现同样的功能。(递归法、后插反转法等)。算法的学习道路还很深，希望自己能够借此机会锻炼自己的计算机思维能力。(共勉)。

【参考文献】