My easy understanding Java solution, just like linkedList

  • 0

    This problem is very funny, we can see it as a linkedList with a loop, find the duplicate one is like find the loop head.
    So we can use fast and slow pointer to handle it.
    For example:
    2-9-1-5-3-6-8-7-9..... , 9 is the loop head, but slow and fast meets at 7, so we can set another newSlow, and goes one step with slow, until meets each other.

     public int findDuplicate(int[] nums) {
            int slow = nums[0], fast = nums[0];
            while (true) {
                slow = nums[slow];
                fast = nums[nums[fast]];
                if (slow == fast) {
            int newSlow = nums[0];
            while (newSlow != slow) {
                newSlow = nums[newSlow];
                slow = nums[slow];
            return slow;

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.