- 关键字：链表、双指针
- 难度：easy
- 题目大意：检测给定的链表是否存在环
题目：
Given a linked list, determine if it has a cycle in it.
Can you solve it using *O(1)* (i.e. constant) memory?
解题思路：
1、采用双指针，起始双指针均指向头结点，fast指针每次走两步，slow指针每次走一步，如果有环，fast和slow最终会相遇。
2、（假设链表无重复节点）也可以采用map记录链表的每一个节点，如果包含重复节点，直接return true；否则，return false。
AC代码
/**
* 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 slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return true;
}
}
return false;
}
}
下面的代码也可以AC，严格来讲，如果链表节点的值有重复，这种解法是错误的（ 看了solution，题目貌似默认链表无重复节点），例如：Testcase：input：[2,2,2,-4] -1
/**
* 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) {
fast = fast.next.next;
slow = slow.next;
if(fast!=null&&slow!=null) {
if(fast.val==slow.val) { //节点值相等时，该方法错误
return true;
}
}
}
return false;
}
}
