链表反转与双向链表就是这么简单

作者: | 更新日期:

检验你是否对链表是真爱的时候到了

本文首发于公众号:天空的代码世界,微信号:tiankonguse
原文地址:https://mp.weixin.qq.com/s/UB1_uHMhFVrLTPtusb_NJQ

一、最后

上一篇文章《面试中必问的几道链表问题》给你们讲解了几道链表相关的面试题。

其实,我不认为那些是好的面试题。
毕竟快慢指针的方法属于启发式算法,不是谁都能想到的。
并且那些题与链表的关系不太大。

链表的重点应该在于指针的操作。

比如我在上篇文章最后,问大家都遇到链表的什么问题。
有一个人回复说:链表实现快速排序。
链表实现快排也很简单,不过这篇文章暂时不讲解,大家可以先思考一下。

这篇文章我们就来体验一些操作链表的乐趣吧

二、反转链表

题意:给一个链表,求反转后的链表。

思路:遍历链表,每次删除一个节点,然后插入到最前面即可。

三、移除链表元素

题意:给一个链表,求删除指定值后的链表。

思路:遍历链表,判断是否等于指定值,等于则删除。
注意实现:由于删除节点的时候,上一个节点需要执行下一个节点,所以我们需要保存上一个节点的指针。

四、奇偶链表

题意:给一个链表,求按奇偶位置将链表分为两部分,奇数的在前面,偶数的在后面。

思路:这个使用双指针思路很容易处理。
前面的指针指向已处理好的奇数部分的最后,后面的指针正常遍历链表。
当后面指针是奇数位置时,将对应的节点删除,插入到前面的之后后面,然后维护两个指针的偏移量即可。

五、回文链表

题意:给一个链表,求判断这个链表是不是回文链表。
要求:使用O(n)的时间复杂度,O(1)的空间复杂度。

思路:这里解释一下要求的含义。
O(n)的时间复杂度并不是说只能循环n次,而是要接近n次。甚至循环2n次也是可以的。
O(1)的空间复杂度并不是说只能定义一个变量,而是不能定义n个空间,定义几个变量都是没问题的。

回到这道题。
回文的意思指的是,一个串正着看和倒着看完全一样。

对于数组,一般从首尾两头逐渐向中间移动,遍历一半就可以判断出是否是回文。
链表的难点在于只能从前到后,不能从后到前。

所以这里我们需要想办法来从后到前遍历其中一半的链表。
简单思考一下,你是不是想到了对后半段链表进行反转呢?
换句话说就是将一个链表拆分为两个链表,然后反转其中一个,他们对比应该是一样的(假设两个长度一样)。

由于链表有可能是奇数长度,这样其中一个的长度比另一个大一。
此时你只需要反转后面那个链表,忽略长链表最后一个元素即可。

六、双向链表

题意:自己实现一个双向链表。

思路:双向链表,顾名思义,不仅像单向链表那样有一个向后的next指针,还有一个向前的prev指针。

这时候,链表插入或删除一个节点的时候,不仅需要维护next指针,还需要维护prev指针。

插入一个节点cur的时候,cur需要先指向上一个节点和下一个节点。

然后上一个节点的next 和 下一个节点的prev都指向当前节点。

删除一个节点的时候,简单一下。
上一个节点直接指向cur的下一个节点,而cur的下一个节点指向cur的上一个节点即可。

当然,这两个操作有一个注意实现。
那就是操作链表头和链表尾的时候,需要先判断上一个节点和下一个节点是否存在。
不存在就不需要操作了。

七、最后

好了,这里给你们介绍一些简单的链表算法,如反转链表,删除指定值。也给你们介绍了双向链表。

到目前为止,这些都是比较简单的操作,下面文章我们来看看链表的高级操作吧。

-EOF-

本文首发于公众号:天空的代码世界,微信号:tiankonguse
如果你想留言,可以在微信里面打开下面的地址进行留言。如果下面没有地址,可以关注公众号留言。
原文地址:https://mp.weixin.qq.com/s/UB1_uHMhFVrLTPtusb_NJQ

点击查看评论

关注公众号,接收最新消息

关注小密圈,学习各种算法

tiankonguse +
穿越