环形链表 Posted on 2021-07-11 00:00:00 2021-07-12 00:00:00 by Author 摘要 给定一个链表和一个头指针,你能判断链表是否是一个环形链表吗???? # 环形链表 1. 题目描述:给定一个链表,判断链表中是否有环。如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。 为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。如果链表中存在环,则返回 true 。 否则,返回 false 。 2. 题目描述: - 示例一: - 输入:head = [3,2,0,-4], pos = 1 - 输出:true - 解释:链表中有一个环,其尾部连接到第二个节点。 - 示例二: - 输入:head = [1,2], pos = 0 - 输出:true - 解释:链表中有一个环,其尾部连接到第一个节点。 - 示例三: - 输入:head = [1], pos = -1 - 输出:false - 解释:链表中没有环。 3. 解题思路:对于这道题,可以使用双指针解法,具体思想如下:定义两个指针,一个快指针(fast),一个慢指针(slow),fast每次移动两步,slow指针每次移动一步,假如链表中有环,那么快指针与慢指针总会相遇,我们不管快指针到底移动了多少步,总会在某次快慢指针相遇,返回true。假如链表中没有环,那么快指针就会提前到达链表尾部。结束循环,返回false。具体实现细节,见如下代码。 4. 代码实现: ```java public boolean hasCycle(ListNode head) { //定义一个返回结果的标志位 boolean flag = false; //定义两个指针,快指针与慢指针,分别指向链表头部 ListNode slowPoint = head, fastPoint = head; //如果有环,直到快指针与慢指针指向同一个节点时推出循环,并且flag=true //为什么要判断fastPoint.next!=null, 这是为了fast指针移动两部时,第二步移动需要第一步节点的存在。 //不然会报空指针异常 while (fastPoint != null && fastPoint.next != null) { //快指针移动两部 fastPoint = fastPoint.next.next; //慢指针移动一步 slowPoint = slowPoint.next; //如果快慢指针指向同一个节点,结束循环,flag=true,说明有环 if (slowPoint == fastPoint) { flag = true; break; } } //返回最终结果 return flag; } ```
{{ item.content }}
{{ child.content }}