环形链表 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 }}