[LintCode] Linked List Cycle I & II

用戶83 發(fā)布于2019-08-14 15:17 / 3487人閱讀

摘要：做法如果有環(huán)，快慢指針必定可以相遇。而讓此時重新從起點出發(fā)，以和相同的速度，需要走非環(huán)路的直線長度，才能到達環(huán)的起點。也就是說，，就是第二個循環(huán)結(jié)束的條件。

Linked List Cycle I Problem

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

Example

Given -21->10->4->5, tail connects to node index 1, return true

Note

做法：如果有環(huán)，快慢指針必定可以相遇。
注意兩點：初始化快慢指針的時候，fast要在slow后面，也就是head.next；由于fast一次走兩步，所以while循環(huán)里要判斷兩個位置是否為null：fast和fast.next。

Solution

public class Solution {
    public boolean hasCycle(ListNode head) {  
        if (head == null/* ||head.next == null */) return false;
        ListNode fast = head.next;
        ListNode slow = head;
        while (fast != slow) {
            if (fast == null || fast.next == null) return false;
            fast = fast.next.next;
            slow = slow.next;
        }
        return true;
    }
}

Linked List Cycle II Problem

Given a linked list, return the node where the cycle begins.

If there is no cycle, return null.

Example

Given -21->10->4->5, tail connects to node index 1，return 10.

Note

畫一個簡圖：

a: length of non-loop 非環(huán)直線的長度
b: length of loop     環(huán)的長度
x: the point slow and fast meet in the loop 快慢指針在環(huán)內(nèi)相遇的位置

--------oooo
        o  o
        ooxo

(a+x)*2 = a-1+kb+x --> a = kb-1-x, slow needs to go kb-x longer to finish the loop.
so if head wants to go to the start point of the loop, it would pass a, the same for slow. After head went a, slow went kb-x-1. However, a = kb-x-1, so head is slow.next at the loop, which is the start point of the loop.

slow在fast在環(huán)里的k處相遇，fast比slow走了兩倍的路程，假設(shè)非環(huán)路和環(huán)路長度分別為a和b，且fast已經(jīng)在環(huán)里多走了k圈，所以：
(a+x)*2 = a-1+kb+x --> a = kb-1-x
此時，slow還要走kb-x才能走完整個環(huán)。
而讓head此時重新從起點出發(fā)，以和slow相同的速度，需要走非環(huán)路的直線長度a，才能到達環(huán)的起點。
那么，head到達環(huán)的時候，走了a = kb-1-x：是slow在環(huán)內(nèi)走到環(huán)的起點的路程-1。
也就是說，slow.next = head，就是第二個while循環(huán)結(jié)束的條件。

Solution

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