关于一道小题目的思考:链表List转置

嗯,这里是简介,主题配置内可以修改,如留空则不显示

关于一道小题目的思考:链表List转置

参见一家公司遇到的这个简单问题,当时头脑一蒙想了很多,很多问题再平时遇到了感觉不以为然,但是真的到面试的时候做的时候就会漏洞百出,因此不管是什么方法还是详细的静下心来看比较好,虽然你永远看不完所有的算法,但是就是慢慢这样的积累的吧。

关于链表逆置的方式有很多,我当时想到的是找到中间节点,然后设置2个指针,然后分别向两边移动,直到到达结尾就ok了,没想到啊,回来验证了一下发现不行,这是链表啊!!!!不是顺序表,不能从后面一个找到前面的元素,幸亏当时只是在等的时候写的玩玩的。哎,太不靠谱了。

回来之后把整个问题想了一遍,加上类似的问题:将单链表内容逆序输出。

“将单链表内容逆序输出”的方法和“链表逆置”很大部分相同,但是也有不同,完全根据需求来。

在之前需要重复一下让自己记得:链表要考虑指针!!!!!!!!

方法1:使用栈。

栈是先入后出的结构,对于只是输入的话:如果不能够改变原来单链表的结构,就只能用栈的结构,全部入栈,接着以此出栈即可。

如果能够改变原来list结构(一般不能)可以使用方法2.

方法2:交换指针

对于逆置,一般使用交换指针的策略,就是遍历一遍,然后把指针变为相反的即可,但是需要注意的是不能把list给断了。

如果能够开辟额外的空间,可以使用方法1中的栈的方式。

 

总结:其实很多算法都是通用的,掌握规律,熟能生巧。

 


发表评论

必填

选填

选填

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

Hello world. 豫ICP备16008819号-1.

Power by Z-BlogPHP  Theme by wzdaxue