Find the Duplicate Number

Problem: Find the Duplication Number

We can consider this problem as a cycle in linked list problem. We take value j at position i as node i pointing to node j. If there's no duplicate, we should form a perfect linked list in this way. However, if there's duplicate, which means there are multiple nodes point to node x, then there will be a cycle at node x. Thus we can use two pointers to find the cycle start point.

Code in Python:

class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        slow = fast = 0
        while True:
            slow, fast = nums[slow], nums[nums[fast]]
            if slow == fast:
                break
        slow = 0
        while slow != fast:
            slow, fast = nums[slow], nums[fast]
        return slow