郑州做订货网站,外贸seo关键词,大型门户网站制作教程,sae部署wordpress1.题目
给你一个链表的头节点 head #xff0c;判断链表中是否有环。
如果链表中有某个节点#xff0c;可以通过连续跟踪 next 指针再次到达#xff0c;则链表中存在环。 为了表示给定链表中的环#xff0c;评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置判断链表中是否有环。
如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。注意pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 则返回 true 。 否则返回 false 。
2.示例
示例 1 输入head [3,2,0,-4], pos 1 输出true 解释链表中有一个环其尾部连接到第二个节点。 示例 2 输入head [1,2], pos 0 输出true 解释链表中有一个环其尾部连接到第一个节点。 示例 3 输入head [1], pos -1 输出false 解释链表中没有环 提示链表中的结构体
/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }*/
3.思路
快慢指针
像这种循环题目或者是追逐的题目就可以使用快慢指针算法由于是循环的那么除非快指针先找到null的情况下快慢指针必定相遇并且两者的相遇也就意味着链表的循环因为一般情况下快指针是走的快的慢指针走的慢而两者速度明显不同的情况下却相遇了那就说明链表是循环的
哈希集合
由于循环最后就是查看是否有重合后的地址那么只需要在往下遍历的时候将链表节点地址保存起来在下一次遍历的时候如果下一个节点地址已经存在与哈希表中时候那么也就意味着链表是循环的
4.代码
LeetCode代码
快慢指针
public class Solution {public boolean hasCycle(ListNode head) {if (head null || head.next null) {return false; // 链表为空或只有一个节点必然无环}ListNode slowIndex head;ListNode fastIndex head;while (fastIndex ! null fastIndex.next ! null) {slowIndex slowIndex.next; // 慢指针每次移动一个节点fastIndex fastIndex.next.next; // 快指针每次移动两个节点if (slowIndex fastIndex) {return true; // 快慢指针相遇存在环}}return false; // 快指针到达链表尾部无环}
} 时间复杂度O(n)空间复杂度O(1) 哈希集合
public class Solution {public boolean hasCycle(ListNode head) {SetListNode set new HashSet();if(headnull || head.nextnull){return false;}while(head.next!null){if(set.contains(head)){return true;}else{set.add(head);head head.next;}}return false;}
} 时间复杂度O(n)空间复杂度O(n) 会了试试挑战下一题♪∀● ●´∀♪
LeetCode150道面试经典题-- 合并两个有序链表(简单)_Alphamilk的博客-CSDN博客
