当前位置:网站首页>链表的常见算法总结
链表的常见算法总结
2020-11-06 01:18:00 【ClawHub的博客】
1、两个单链表求和
445. 两数相加 II
双栈法更好理解。
1 |
public static ListNode addTwoNumbers(ListNode l1, ListNode l2) { |
将两个链表构造两个栈,使用栈先进后出的特性,做两个链表倒叙做计算,注意进位的情况。
2、单链表非递归翻转,不借助其他数据结构
206. 反转链表
单链表的翻转就是将相邻两个节点的指针翻转。需要借助两个额外的指针用来存储当前节点的前后节点。
1 |
public static ListNode reverseList(ListNode head) { |
3、回文链表(用 O(n) 时间复杂度和 O(1) 空间复杂度)
234. 回文链表
通过快慢指针获取链表中间节点位置,将后半段链表反转,之后迭代前后链表,判断值是否相同。
1 |
public static boolean isPalindrome(ListNode head) { |
4、环形链表
141. 环形链表
检测链表中是否有环,可以使用两种方法:使用HashSet或者快慢指针。
1 |
public static boolean hasCycle(ListNode head) { |
5、删除链表种所有值为val的节点
203. 移除链表元素
链表移除操作要借助一个哨兵节点,简化删除。
1 |
public static ListNode removeElements(ListNode head, int val) { |
6、合并两个有序链表
21. 合并两个有序链表
需要使用哨兵节点。
1 |
public static ListNode mergeTwoLists(ListNode l1, ListNode l2) { |
总结
链表常用的算法经常会借助快慢指针和哨兵节点。只要用到哨兵节点head就会有pre节点相配合。
版权声明
本文为[ClawHub的博客]所创,转载请带上原文链接,感谢
https://clawhub.club/posts/2020/01/06/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/%E9%93%BE%E8%A1%A8%E7%9A%84%E5%B8%B8%E8%A7%81%E7%AE%97%E6%B3%95%E6%80%BB%E7%BB%93/
边栏推荐
猜你喜欢
随机推荐
用Keras LSTM构建编码器-解码器模型
有关PDF417条码码制的结构介绍
自然语言处理-搜索中常用的bm25
Polkadot series (2) -- detailed explanation of mixed consensus
自然语言处理-错字识别(基于Python)kenlm、pycorrector
7.3.1 file upload and zero XML registration interceptor
Network programming NiO: Bio and NiO
Probabilistic linear regression with uncertain weights
Top 10 best big data analysis tools in 2020
连肝三个通宵,JVM77道高频面试题详细分析,就这?
通过深层神经网络生成音乐
10 easy to use automated testing tools
Pycharm快捷键 自定义功能形式
读取、创建和运行多个文件的3个Python技巧
简直骚操作,ThreadLocal还能当缓存用
什么是无副作用的函数方法?如何取名? - Mario
使用NLP和ML来提取和构造Web数据
Basic principle and application of iptables
Azure Data Factory(三)整合 Azure Devops 實現CI/CD
连肝三个通宵,JVM77道高频面试题详细分析,就这?