8上的信息课做网站作业,湖南旅游网站开发,阿里云服务器建设网站选择那个镜像,网站建设 html1.问题描述 给你一个链表的头节点 head #xff0c;判断链表中是否有环 示例1 输入#xff1a;head [3,2,0,-4], pos 1
输出#xff1a;true
解释#xff1a;链表中有一个环#xff0c;其尾部连接到第二个节点 示例2 输入#xff1a;head [1,2], pos 0
输出#xf…1.问题描述 给你一个链表的头节点 head 判断链表中是否有环 示例1 输入head [3,2,0,-4], pos 1
输出true
解释链表中有一个环其尾部连接到第二个节点 示例2 输入head [1,2], pos 0
输出true
解释链表中有一个环其尾部连接到第一个节点。 示例3 输入head [1], pos -1
输出false
解释链表中没有环。 提示
链表中节点的数目范围是 [0, 104]-105 Node.val 105pos 为 -1 或者链表中的一个 有效索引 难度等级 简单 题目链接 环形链表
2.解题思路 这道环形链表的问题相当容易解决有点像我们小学时候的追及问题。我们定义两个快慢指针来模拟两个人相互追及。 //快指针ListNode fast head;//慢指针ListNode slow head; 如果链表真的是环形链表的话它就会形成一个圈那么我们的快慢指针相当于两个人从同一个入口进入一个闭环的操场在跑步。快的那个人只要时间足够就可以比慢的那个人多跑一圈而相遇。 我们假设快指针的步频为2慢指针步频为1如果快指针能走到尽头遇到null说明不是环形链表如果与慢指针相遇说明是环形链表。 //遍历while(fast ! null fast.next ! null){//慢指针一次走一步slow slow.next;//快指针一次走两步fast fast.next.next;if(slow fast){return true;}}return false;
3.代码展示
/*** 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) {//快指针ListNode fast head;//慢指针ListNode slow head;//遍历while(fast ! null fast.next ! null){//慢指针一次走一步slow slow.next;//快指针一次走两步fast fast.next.next;if(slow fast){return true;}}return false;}
}
4.总结 这道环形链表的题我们当成小学的追及相遇问题就可以轻松解决了。祝大家刷题愉快~
