10_141. 环形链表
2022/3/3 6:15:16
本文主要是介绍10_141. 环形链表,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目描述:
解题思路:
- 判断是否有环,第一反应是想着为每一个节点,能有一个类似pos的标识,当再次出现这个pos时,就可以判定是否有环了。于是想起了HashMap可以将每一个节点和pos映射起来。
- 题解中使用了HashSet,因为题目不考虑要返回具体的pos值,因此只需要判别Hash表中是否存在重复的节点即可,而HashSet的add方法,可以判别是否加入了重复的元素
- 快慢指针,快指针每次移动两个,慢指针每次移动一个,如果存在环的话,快指针一定会追上慢指针。对于细节问题,考虑以下两点:
- 果使用fast=slow=head,在while循环体里面就会导致进不去循环,要么这样更改,要么就改成do...while循环
- 如果不加入fast.next==null条件,当fast.next为null时,下面的语句fast.next.next就会报错。
代码
HashMap
//**********HashMap /** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public boolean hasCycle(ListNode head) { if (head == null || head.next == null){ return false; } HashMap<ListNode,Integer> map = new HashMap<>(); int pos = 0; map.put(head,pos); while (head.next != null){ head = head.next; if (map.containsKey(head)){ return true; } map.put(head,++pos); } return false; } }
HashSet
//*********HashSet /** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public boolean hasCycle(ListNode head) { Set<ListNode> seen = new HashSet<ListNode>(); while (head != null) { if (!seen.add(head)) { return true; } head = head.next; } return false; } }
快慢指针
//*******快慢指针 /** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public boolean hasCycle(ListNode head) { if (head == null || head.next == null){ return false; } ListNode fast = head.next;//如果使用fast=slow=head,在while循环体里面就会导致进不去循环,要么这样更改,要么就改成do...while循环 ListNode slow = head; while (fast != slow ){ if (fast == null || fast.next == null){//这里如果不加入fast.next==null条件,当fast.next为null时,下面的语句fast.next.next就会报错。 return false; } fast = fast.next.next; slow = slow.next; } return true; } }
这篇关于10_141. 环形链表的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-04-17基于SpringWeb MultipartFile文件上传、下载功能
- 2024-04-14个人开发者,Spring Boot 项目如何部署
- 2024-04-14RAG应用开发实战02-相似性检索的关键 - Embedding
- 2024-04-14出海软件草根逆袭打法是什么?
- 2024-04-13鸿蒙原生应用再新丁!企查查 碧蓝航线 入局鸿蒙
- 2024-04-11RAG应用开发实战(01)-RAG应用框架和解析器
- 2024-04-10DevOps已死?2024年的DevOps将如何发展
- 2024-04-10码农必看:常见源代码混淆技术详解
- 2024-04-07以一当十丨TiDB 在东吴证券秀财 APP 的应用实践
- 2024-04-07月活超 1.1 亿,用户超 4 亿,你也在用的「知乎」是如何在超大规模 TiDB 集群上玩转多云多活的?来听听知乎代晓磊的答案!