本文共 972 字,大约阅读时间需要 3 分钟。
从第一次相遇可得:slow: a + b; fast: 2(a + b). 并且2a + 2b = a + b + n(b + c), 可得a = (n - 1)b + nc,以此slow移到head,然后slow和fast都每次移动一位,最后相遇位置就是环开头。
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */public class Solution { public ListNode detectCycle(ListNode head) { if (head == null || head.next == null) { return null; } ListNode fast = head.next.next; ListNode slow = head.next; while (fast != null && fast.next != null) { if (fast == slow) { break; } fast = fast.next.next; slow = slow.next; } if (fast == null || fast.next == null) { return null; } slow = head; // 这里fast也是每次移一位! while (fast != slow) { slow = slow.next; fast = fast.next; } return slow; }}