null
.
Follow up:
Can you solve it without using extra space?
/** * 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) { // Suppose the non-cycle length is X // Suppose the cycle length is Y // Suppose fast pointer and slow pointer encounter on the Kth node of cycle // So when both encountered, slow steps = X + nY + K; fast steps = X + mY + K (Note: m > n) // We can deduce X + K = (m-2n)Y // Therefore, if slow pointer run X steps from the Kth node, it will return to the beginning of cycle. ListNode fast = head, slow = head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; if (fast == slow) { fast = head; while (fast != slow) { fast = fast.next; slow = slow.next; } return fast; } } return null; } }
No comments:
Post a Comment