LCOF22_II

[underwindfall]

• https://leetcode-cn.com/problems/c32eOV/

• 思路

  • 快慢指针
  • a + (n)(b + c) + b = 2 (a + b) ==== a = (n-1)b + c

• [x] 刷15mins

• [x] 刷5mins

// time O(n)
    // space O(1)
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head, slow = head;
        while (fast != null) {
            if (fast.next != null) {
                fast = fast.next.next;
            } else {
                return null;
            }
            slow = slow.next;
            if (fast == slow) {
                break;
            }
        }

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