141. 环形链表

141. 环形链表

快慢指针版本一

public class Solution {
    // 使用快慢指针法，快指针每次走两步，慢指针每次走一步，如果链表有环，则快慢指针一定会相遇
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;
        // 快指针
        ListNode fast = head.next;
        // 慢指针
        ListNode slow = head;
        while (fast != slow) {
            // 如果为空，说明跑完了，没有环，返回 false
            if (fast == null || fast.next == null) return false;
            fast = fast.next.next;
            slow = slow.next;
        }
        return true;
    }
}

快慢指针版本二

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;
        // 慢指针
        ListNode fast = head.next;
        // 快指针
        ListNode slow = head;
        // 如果快指针与快指针的下个节点都不为空，则继续遍历
        // 为什么判断快指针？因为快指针先到达终点，如果链表没有环，到终点时为空
        while (fast != null && fast.next != null) {
            // 如果快指针与慢指针相等，说明相遇了，返回 true
            if (fast == slow) return true;
            slow = slow.next;
            fast = fast.next.next;
        }
        return false;
    }
}

使用 set 存放节点

public class Solution {
    // 使用一个 set 记录遍历过的节点
    public boolean hasCycle(ListNode head) {
        if (head == null) return false;
        Set<ListNode> set = new HashSet<>();
        while (head != null) {
            // 如果节点在 set 中，说明有环
            if (set.contains(head)) return true;
            set.add(head);
            head = head.next;
        }
        return false;
    }
}