环形链表「变题」

141. 环形链表

开头先来一个小插曲，关于「单链表」相关的总结可见 单链表的六大解题套路

// 快慢指针 (判断是否有环)
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;
}

变题一：找到环入口

题目详情可见 环形链表 II

算法思想一致的题目：寻找重复数

public ListNode detectCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            slow = head;
            while (slow != fast) {
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }
    }
    return null;
}

变题二：计算环中节点数

public int detectCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            int cnt = 0;
            // 再走一圈
            do {
                slow = slow.next;
                cnt++;
            } while (slow != fast);
            return cnt;
        }
    }
    return 0;
}

其它方法：Set

// 判断是否有环 且 找到环入口
public ListNode detectCycle(ListNode head) {
    Set<String> set = new HashSet<>();
    ListNode p = head;
    while (p != null) {
        int sz = set.size();
        set.add(p.toString());
        // 找到环入口
        if (sz == set.size()) {
            return p;
        }
        p = p.next;
    }
    return null;
}