Linked List Cycle II

  • medium
  • math
  • similar: 规律题

思路

  • 使用九章算法的方法, 但是老是记不住! 总是搞混.
  • 再次复习一遍, 有circle就说明slow/fast会相遇. 等到相遇后, 将slow重置为head, 那么当slow == fast.next的时候, slow的位置就是cycle入口.

idea

  • 九章的标准写法, 代码如下:
public ListNode detectCycle(ListNode head) {
    if (head == null || head.next == null) {
      return null;
    }
    ListNode fast = head.next , slow = head;
    while (fast != slow) {
      if (fast == null || fast.next == null)  return null;
      fast = fast.next.next;
      slow = slow.next;
    }
    slow = head;
    while (fast.next != slow) {
      fast = fast.next;
      slow = slow.next;
    }
    return slow;
}