单链表逆序

忘是亡心i 2022-09-25 13:24 163阅读 0赞

**2、 单链表逆序**

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

![1337526379_6285.jpg][]

图（1）初始状态

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

![1337526423_9040.jpg][]

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

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

head->next = prev;

prev = head;

head = next;

next = head->next;

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

![1337526569_3801.jpg][]

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

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

![1337526604_2684.jpg][]

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

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

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

prev = NULL;

循环迭代体是：

next = head->next;

head->next = prev;

prev = head;

head = next;

循环终止条件是：

head == NULL

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

<table style="color:rgb(51,51,51); font-family:Arial; font-size:14px; line-height:25px"> 
 <tbody> 
 <tr> 
 <td align="left"> 
 <div style="font-family:Consolas; color:black; font-size:11pt; background-color:rgb(166,202,240)"> 
 &nbsp;&nbsp;&nbsp;61&nbsp;LINK_NODE&nbsp;*ReverseLink(LINK_NODE&nbsp;*head) 
 &nbsp;&nbsp;&nbsp;62&nbsp;{ 
 &nbsp;&nbsp;&nbsp;63&nbsp;&nbsp;&nbsp;&nbsp; LINK_NODE&nbsp;*next; 
 &nbsp;&nbsp;&nbsp;64&nbsp;&nbsp;&nbsp;&nbsp; LINK_NODE&nbsp;*prev&nbsp;=&nbsp;NULL; 
 &nbsp;&nbsp;&nbsp;65&nbsp; 
 &nbsp;&nbsp;&nbsp;66&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;while(head&nbsp;!=&nbsp;NULL) 
 &nbsp;&nbsp;&nbsp;67&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;{ 
 &nbsp;&nbsp;&nbsp;68&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; next&nbsp;=&nbsp;head-&gt;next; 
 &nbsp;&nbsp;&nbsp;69&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; head-&gt;next&nbsp;=&nbsp;prev; 
 &nbsp;&nbsp;&nbsp;70&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; prev&nbsp;=&nbsp;head; 
 &nbsp;&nbsp;&nbsp;71&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp; head&nbsp;=&nbsp;next; 
 &nbsp;&nbsp;&nbsp;72&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;} 
 &nbsp;&nbsp;&nbsp;73&nbsp; 
 &nbsp;&nbsp;&nbsp;74&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;prev; 
 &nbsp;&nbsp;&nbsp;75&nbsp;} 
 </div> </td> 
 </tr> 
 </tbody> 
</table>

现在，我们用递归的思想来分析这个问题。先假设有这样一个函数，可以将以head为头节点的单链表逆序，并返回新的头节点指针，应该是这个样子：

现在利用ReverseLink2()对问题进行求解，将链表分为当前表头节点和其余节点，递归的思想就是，先将当前的表头节点从链表中拆出来，然后对剩余的节点进行逆序，最后将当前的表头节点连接到新链表的尾部。第一次递归调用ReverseLink2(head->next)函数时的状态如图（5）所示：

![1337526710_9340.jpg][]

图（5）第一次递归状态图

这里边的关键点是头节点head的下一个节点head->next将是逆序后的新链表的尾节点，也就是说，被摘除的头接点head需要被连接到head->next才能完成整个链表的逆序，递归算法的核心就是一下几行代码：

现在顺着这个思路再进行一次递归，就得到第二次递归的状态图：

![1337526773_8331.jpg][]

图（6）第二次递归状态图

再进行一次递归分析，就能清楚地看到递归终止条件了：

![1337526800_1048.jpg][]

图（7）第三次递归状态图

递归终止条件就是链表只剩一个节点时直接返回这个节点的指针。可以看出这个算法的核心其实是在回朔部分，递归的目的是遍历到链表的尾节点，然后通过逐级回朔将节点的next指针翻转过来。递归算法的完整代码如下：

<table style="color:rgb(51,51,51); font-family:Arial; font-size:14px; line-height:25px"> 
 <tbody> 
 <tr> 
 <td align="left"> 
 <div style="font-family:Consolas; color:black; font-size:11pt; background-color:rgb(166,202,240)"> 
 &nbsp;&nbsp;&nbsp;77&nbsp;LINK_NODE&nbsp;*ReverseLink2(LINK_NODE&nbsp;*head) 
 &nbsp;&nbsp;&nbsp;78&nbsp;{ 
 &nbsp;&nbsp;&nbsp;79&nbsp;&nbsp;&nbsp;&nbsp; LINK_NODE&nbsp;*newHead; 
 &nbsp;&nbsp;&nbsp;80&nbsp; 
 &nbsp;&nbsp;&nbsp;81&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if((head&nbsp;==&nbsp;NULL)&nbsp;||&nbsp;(head-&gt;next&nbsp;==&nbsp;NULL)) 
 &nbsp;&nbsp;&nbsp;82&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;head; 
 &nbsp;&nbsp;&nbsp;83&nbsp; 
 &nbsp;&nbsp;&nbsp;84&nbsp;&nbsp;&nbsp;&nbsp; newHead&nbsp;=&nbsp;ReverseLink2(head-&gt;next);&nbsp;/*递归部分*/ 
 &nbsp;&nbsp;&nbsp;85&nbsp;&nbsp;&nbsp;&nbsp; head-&gt;next-&gt;next&nbsp;=&nbsp;head;&nbsp;/*回朔部分*/ 
 &nbsp;&nbsp;&nbsp;86&nbsp;&nbsp;&nbsp;&nbsp; head-&gt;next&nbsp;=&nbsp;NULL; 
 &nbsp;&nbsp;&nbsp;87&nbsp; 
 &nbsp;&nbsp;&nbsp;88&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return&nbsp;newHead; 
 &nbsp;&nbsp;&nbsp;89&nbsp;} 
 </div> </td> 
 </tr> 
 </tbody> 
</table>

循环还是递归？这是个问题。当面对一个问题的时候，不能一概认为哪种算法好，哪种不好，而是要根据问题的类型和规模作出选择。对于线性数据结构，比较适合用迭代循环方法，而对于树状数据结构，比如二叉树，递归方法则非常简洁优雅。

[1337526379_6285.jpg]: https://img-my.csdn.net/uploads/201205/20/1337526379_6285.jpg
[1337526423_9040.jpg]: https://img-my.csdn.net/uploads/201205/20/1337526423_9040.jpg
[1337526569_3801.jpg]: https://img-my.csdn.net/uploads/201205/20/1337526569_3801.jpg
[1337526604_2684.jpg]: https://img-my.csdn.net/uploads/201205/20/1337526604_2684.jpg
[1337526710_9340.jpg]: https://img-my.csdn.net/uploads/201205/20/1337526710_9340.jpg
[1337526773_8331.jpg]: https://img-my.csdn.net/uploads/201205/20/1337526773_8331.jpg
[1337526800_1048.jpg]: https://img-my.csdn.net/uploads/201205/20/1337526800_1048.jpg