Algorithm Challenge #4




Algorithm Challenge
Algorithms
10 Best Coding Challenge Websites for 2018
Algorithm Challenge
Algorithm Challenge #4
Solve Any Code Challenge or Algorithm
Algorithms
most popular coding challenge websites for 2017


141. Linked List Cycle

Given a linked list, determine if it has a cycle in it.

Solution



From the left picture. If there’s a cycle in the linked list, two pointer moving in a different steps must meet somewhere in the loop. There for we define two pointer slow and fast. At each step, slow moves one position forward and fast moves two position forward. If fast goes to the end without encounter with slow. Then there’s no cycle.


def isCycle(head):
    if head is None or head.next is None: return
    slow = head
    fast = head.next

    try: 
        while slow != fast:
            slow = slow.next
            fast = fast.next.next
        return True
    except:
        return False




142. Linked List Cycle II


Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.


Solution




Follow by last challenge, now we need to find the entry point. If the distance from start to entrance is H; distance from entrance to meeting point is D; the length of the cycle is L.
Then the distance that the slow pointer walk through is H + D. The fast point walks double distance 2(H+D)+1. And the difference between former and later must be the multiplication of L. Thus, we have d_fast-d_slow = H + D +1= L ->
 H +1= L-D.
That is to say, the distance from the head to the entrance is the same as from encounter point to the entrance. As a result, if two pointer move from head+1 and encounter point respectively, they will eventually meet at the entrance.

def findEntrance(head):
    # Base case #same as finding cycle
    if head is None or head.next is None: return
    slow = head
    fast = head.next
    
    try: 
        while slow != fast:
            slow = slow.next
            fast = fast.next.next
        return True
    except:
        return False

    p1 = head.next
    p2 = slow
    while p1!=p2:
        p1 = p1.next
        p2 = p2.next
    return p1
287. Find the Duplicate Number Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one. You must not modify the array (assume the array is read only). You must use only constant, O(1) extra space. Your runtime complexity should be less than O(n2). There is only one duplicate number in the array, but it could be repeated more than once. Solution We cannot use sorting, dynamic programing and loop check. It is actually a variant of Linked list cycle problem. The number in the list for 1 to length of list can be consider as the index to the next position. Therefore, for the list as following, we can think about from 
Input: 

[1,3,4,2,2]

Output: 2

1 -> 3 -> (cycle start) 2 ->4->2->4-> ……

num[0] -> num[1] -> num[3] -> num[2]->num[4]->num[2]-> ……

The entrance of cycle must be the duplicate element in the list. We are actually looking for the entrance! Therefore we can write down the solution the same as last challenge with minimal modification. 



def findDuplicate(nums):
    if len(nums) <2:  return 
    slow = nums[0]
    fast = nums[nums[0]]
    while slow!=fast:
        slow = nums[slow]
        fast = nums[nums[fast]]
    p1 = nums[slow]
    p2 = nums[0]
    while p1!=p2:
        p1 = nums[p1]
        p2 = nums[p2]
    return p1