q141_环形链表

1

package 快慢指针遍历.q141_环形链表.f1;
public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
    }
}
package 快慢指针遍历.q141_环形链表.f1;
import java.util.HashSet;
import java.util.Set;
/**
 * 哈希表 o(n)
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> nodesSeen = new HashSet<>();
        while (head != null) {
            if (nodesSeen.contains(head)) {
                return true;
            } else {
                nodesSeen.add(head);
            }
            head = head.next;
        }
        return false;
    }
}

2

package 快慢指针遍历.q141_环形链表.f2;
public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
    }
}
package 快慢指针遍历.q141_环形链表.f2;
/**
 * 快慢指针 o(n)
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while (slow != fast) {
            if (fast == null || fast.next == null) {
                return false;
            }
            slow = slow.next;
            fast = fast.next.next;
        }
        return true;
    }
}