当前位置:网站首页>链表的常见算法总结
链表的常见算法总结
2020-11-06 01:18:17 【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/
边栏推荐
- C++ 数字、string和char*的转换
- C++学习——centos7上部署C++开发环境
- C++学习——一步步学会写Makefile
- C++学习——临时对象的产生与优化
- C++学习——对象的引用的用法
- C++编程经验(6):使用C++风格的类型转换
- Won the CKA + CKS certificate with the highest gold content in kubernetes in 31 days!
- C + + number, string and char * conversion
- C + + Learning -- capacity() and resize() in C + +
- C + + Learning -- about code performance optimization
猜你喜欢
-
C + + programming experience (6): using C + + style type conversion
-
Latest party and government work report ppt - Park ppt
-
在线身份证号码提取生日工具
-
Online ID number extraction birthday tool
-
️野指针?悬空指针?️ 一文带你搞懂!
-
Field pointer? Dangling pointer? This article will help you understand!
-
HCNA Routing&Switching之GVRP
-
GVRP of hcna Routing & Switching
-
Seq2Seq实现闲聊机器人
-
【闲聊机器人】seq2seq模型的原理
随机推荐
- LeetCode 91. 解码方法
- Seq2seq implements chat robot
- [chat robot] principle of seq2seq model
- Leetcode 91. Decoding method
- HCNA Routing&Switching之GVRP
- GVRP of hcna Routing & Switching
- HDU7016 Random Walk 2
- [Code+#1]Yazid 的新生舞会
- CF1548C The Three Little Pigs
- HDU7033 Typing Contest
- HDU7016 Random Walk 2
- [code + 1] Yazid's freshman ball
- CF1548C The Three Little Pigs
- HDU7033 Typing Contest
- Qt Creator 自动补齐变慢的解决
- HALCON 20.11:如何处理标定助手品质问题
- HALCON 20.11:标定助手使用注意事项
- Solution of QT creator's automatic replenishment slowing down
- Halcon 20.11: how to deal with the quality problem of calibration assistant
- Halcon 20.11: precautions for use of calibration assistant
- “十大科学技术问题”揭晓!|青年科学家50²论坛
- "Top ten scientific and technological issues" announced| Young scientists 50 ² forum
- 求反转链表
- Reverse linked list
- js的数据类型
- JS data type
- 记一次文件读写遇到的bug
- Remember the bug encountered in reading and writing a file
- 单例模式
- Singleton mode
- 在这个 N 多编程语言争霸的世界,C++ 究竟还有没有未来?
- In this world of N programming languages, is there a future for C + +?
- es6模板字符
- js Promise
- js 数组方法 回顾
- ES6 template characters
- js Promise
- JS array method review
- 【Golang】️走进 Go 语言️ 第一课 Hello World
- [golang] go into go language lesson 1 Hello World