o(n) time and o(1) space java solution with Chinese explanation


  • 4
    C

    步骤一:通过Linked List Cycle的方式,则快慢指针(快指针一次两步,慢指针一次一步)相遇时,则表示存在环,且相遇点在环上。
    步骤二:如果环存在,记:
    c表示从head到环起始点的距离;
    s表示从环起始点到快慢指针相遇点的距离;
    cycle表示环的长度;
    distance(pointer)表示指针走过的距离;
    性质:
    a)快指针走过的距离是慢指针走过距离的二倍
    b)快指针和慢指针会相遇,是因为快指针已经套了慢指针一圈(且套第一圈时就会相遇,因为快指针快追上慢指针时,相距要么为1要么为2,为1时,下一次移动后相遇,为2时,在经过两次移动相遇)
    于是有:
    distance(slow)=c+s, distance(fast)=2(c+s)
    性质a和b -> distance(fast)-distanc(slow)=k·cycle=2(c+s) - (c+s) = c+s
    -> c = k·cycle - s
    又由于:环长度为cycle,两指针距离环起点距离为s,在走cycle-s则重新到达起点,所以经过 k·cycle - s=cycle-s +(k-1)cycle也会重新回到起点;且c为从head到环起点的距离,所以从head经过距离c会到达环起点,又c=k·cycle - s;所以用两个指针,同时从快慢指针的相遇点和head出发,每次移动距离为1,经过k·cycle - s会在环起点相遇。

    public ListNode detectCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while(fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
    if(slow == fast){
    slow = head;
    while(slow != fast){
    slow = slow.next;
    fast = fast.next;
    }
    return slow;
    }
    }
    return null;
    }


  • 0
    W

    The algorithm is quite good. But is there something wrong in the explanation?
    性质a和b -> distance(fast)-distanc(slow)=cycle=2(c+s) - (c+s) = c+s
    I think it should be:
    性质a和b -> distance(fast)-distanc(slow)=k*cycle
    Am I right?


  • 0
    C
    This post is deleted!

  • 0
    C

    @WeidongCMU yes, you r right. if distance(c) >> distiance(cycle), then distance(fast)-distanc(slow)=k*cycle, where k > 1. thank u.


Log in to reply
 

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