数据结构和算法设计专题之单链表的逆序

 https://blog.csdn.net/jiangwei0910410003/article/details/37937721

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

图&＃xff08;1&＃xff09;初始状态

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

图&＃xff08;2&＃xff09;经过第一次迭代后的状态

 从图&＃xff08;1&＃xff09;的初始状态到图&＃xff08;2&＃xff09;状态共做了四个操作&＃xff0c;这四个操作的伪代码如下&＃xff1a;

head->next &＃61; prev;

prev &＃61; head;

head &＃61; next;

next &＃61; head->next;

这四行伪代码就是循环算法的迭代体了&＃xff0c;现在用这个迭代体对图&＃xff08;2&＃xff09;的状态再进行一轮迭代&＃xff0c;就得到了图&＃xff08;3&＃xff09;的状态&＃xff1a;

图&＃xff08;3&＃xff09;经过第二次迭代后的状态

         那么循环终止条件呢&＃xff1f;现在对图&＃xff08;3&＃xff09;的状态再迭代一次得到图&＃xff08;4&＃xff09;的状态&＃xff1a;

图&＃xff08;4&＃xff09;经过第三次迭代后的状态

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

        现在来总结一下&＃xff0c;循环的初始条件是&＃xff1a;

prev &＃61; NULL;

循环迭代体是&＃xff1a;

next &＃61; head->next;

head->next &＃61; prev;

prev &＃61; head;

head &＃61; next;

循环终止条件是&＃xff1a;

head &＃61;&＃61; NULL

根据以上分析结果&＃xff0c;逆序单链表的循环算法如下所示&＃xff1a;

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

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

图&＃xff08;5&＃xff09;第一次递归状态图

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

现在顺着这个思路再进行一次递归&＃xff0c;就得到第二次递归的状态图&＃xff1a;

图&＃xff08;6&＃xff09;第二次递归状态图

 再进行一次递归分析&＃xff0c;就能清楚地看到递归终止条件了&＃xff1a;

图&＃xff08;7&＃xff09;第三次递归状态图

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

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