-

2021年1月26日发(作者：月亮的彩虹)
下面来看一下很经典的
“
单链表逆序
”
问题。很多公司的面试题库中 都有这道题，
有的公司明确题目要求不能使用额外的节点存储空间，
有的没有明确说明，
但是
如果面试者使用了额外的节点存储空间做中转，
会得到一个比较低的分数。
如何
在不使用额外存储节点的情况下使一个单链表的所有节点逆序？我们先用迭代
循环的思想来分析 这个问题，链表的初始状态如图（
1
）所示：


图（
1
）初始状态


初始状态，
prev
是
NULL
，
head
指向当前的头节点
A
，
n ext
指向
A
节点的下一
个节点
B
。首先从
A节点开始逆序，将
A
节点的
next
指针指向
prev
，因为
prev
的当前值是
NULL
，所以
A
节点就从链表 中脱离出来了，然后移动
head
和
next
指针，使它们分别指向
B
节点和
B
的下一个节点
C
（因为当前的
next
已经指向
B
节点了，
因此修改
A
节点的
next
指 针不会导致链表丢失）
。
逆向节点
A
之后，
链表的状态如图（
2
）所示：


图（
2
）经过第一次迭代后的状态


从图（
1< br>）的初始状态到图（
2
）状态共做了四个操作，这四个操作的伪代码如
下：


head->next = prev;

prev = head;

head = next;

next = head->next;



这四行伪代码就是循环算法的迭代体了，现在 用这个迭代体对图（
2
）的状态再
进行一轮迭代，就得到了图（
3
） 的状态：


图（
3
）经过第二次迭代后的状态


那么循环终止条件呢？现在对图（
3
）的状态再迭代一次得到图（
4
）的状
态：


图（
4
）经过第三次迭代后的状态


此时可以看出，在图（
4
）的基础上再进行一次迭代就可以完成链表的逆序 ，因
此循环迭代的终止条件就是当前的
head
指针是
NULL
。< br>

现在来总结一下，循环的初始条件是：

prev = NULL;



循环迭代体是：

next = head->next;

head->next = prev;

prev = head;

head = next;



循环终止条件是：

head == NULL



根据以上分析结果，逆序单链表的循环算法如下所示：

61
LINK_NODE
*
ReverseLink
(
LINK_NODE
*
head
)

62

{

63
LINK_NODE
*
next
;

64
LINK_NODE
*
prev
=
NULL
;

65

66

while
(
head
!=
NULL
)

67

{

68
next
=
head
->
next
;

-

-

-

-

-

-

-

-