LinkedListCycle [source code]

public class LinkedListCycle {
static
/******************************************************************************/
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null) return false;
        Set<ListNode> bag = new HashSet<>();
        while (head.next != null) {
            if (!bag.add(head)) break;
            head = head.next;
        }
        return head.next != null;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        LinkedListCycle.Solution tester = new LinkedListCycle.Solution();
    }
}

这个题目的Follow-Up 的要求是no extra space, 这个是因为这种 cycle题, 最基本的思路其实就是用一个类似 count 或者 collect 的思路来做, 就像是之前看到的亚麻的那个"东南西北"的题目一样;
当然我刚开始更像做到的算法, 其实是要么类似 stream 算法, 让当前的iteration 只依赖O(1)的历史信息, 要么就是可以用 Stack 一样的类似的, 只依赖非常 local 的历史信息;

这个题目刚开始的想法是用 DFS 做, 不过用 DFS 依赖一个 visited 的 flag, 这个是没有办法做到的, 因为如果你用一个 asssoc array 来做, 肯定就要 space, 如果你用attribute 来做, 你就要把每一个ListNode 重新 wrap 一下, 这个还是需要额外的空间;

这里先不考虑 Follow-Up 做一个, 使用的方法就是很简单的collect, 不过最后的速度却很不乐观: 7ms (5%). 这个有点奇怪;

Set的常规 API 操作:

java> Set<Integer> bag = new HashSet<>()  
java.util.Set<java.lang.Integer> bag = []  
java> bag.add(1)  
java.lang.Boolean res1 = true  
java> bag.add(2)  
java.lang.Boolean res2 = true  
java> bag  
java.util.Set<java.lang.Integer> bag = [1, 2]  
java> bag.add(1)  
java.lang.Boolean res3 = false

这个是最后的 submission 最优解: 1(7):

public class Solution {  
    public boolean hasCycle(ListNode head) {  
        ListNode slow = head;  
        ListNode fast = head;  

        while(fast != null && fast.next != null) {  
            fast = fast.next.next;  
            slow = slow.next;  
            if(fast == slow) return true;  
        }  
        return false;  
    }  
}

我对于 cycle 问题的理解还是太局限于 graph 算法了, 之前这个算法已经见过一次了, 快慢指针竞速的思路, 还是没有想到;

这个是同样的思路, editorial 里面稍微改写了一下:

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

逻辑好像稍微清晰了一些, 不过本质上好像其实是一样的, 都借助了premature exit, 只不过是不同的 exit 而已;

另外注意一下, 这个龟兔赛跑的思路, 正好还完成了O(1) space 的要求; 我对于这个 Follow-Up 本来的思路就是从每一个 node 开始, 当前 node 存住(prev), 然后new 一个指针向前跑, 直到 null || 等于 prev. 这个做法就是 N^2的时间了, 虽然空间要求倒是达到了;

另外, 你怎么证明这个算法的复杂度?
假如是只有一个cycle, 然后hare 和 tortoise 同时从起点出发, 那么最后其实 iteration 的数量就是 cycle 的长度, 也正好是 tortoise 走过的步数.
如果不是只有一个 cycle, 比如 cycle 前面有一个 line, 那么最后等价的效果其实就是: 只有一个 cycle, 然而 hare 先于 tortoise出发.
思考一下, 跑圈追赶的本质是什么? 其实就是两者之间的相对距离从0开始, 逐渐增加, 直到mod圈长为0; 在过程中,每一个 iteration, 相对距离变化的量是1; 严格来说, 应该是 hare 领先 tortoise 的距离. 如果hare 领先, 那么这个距离就是正值. 因为是一个loop, 所以你永远可以理解为 hare 领先; (这里为什么要这样规定, 就是为了让这个值有一个固定的方向性, 讨论的时候方便一些);
如果是同时出发, 那么相对距离的起点就是0; 如果两个不是同时出发, 那么就相当于相对距离的起点不是0. 那么最后追赶所需要的时间是变多了还是变少了? 注意无论 tortoise 起跑的时候 hare 在什么位置, 其实都可以理解为hare 领先距离是一个正值.
所以有line 的情况下, 实际上的追赶时间反而少了, 也就是少于 cycle 的长度了;
所以最后的cycle 内的时间长度是O(len(cycle)) = O(N).

discussion看到一个成功使用 visited 做到的解:

public class Solution {  
    public boolean hasCycle(ListNode head) {  
        ListNode p = head,pre = head;  
        while(p != null && p.next != null){  
            if (p.next == head) return true;  
            p = p.next;  
            pre.next = head;  
            pre = p;  
        }  
        return false;  
    }  
}

make all the node you visited links to the head ListNode. once you reach a new ListNode,see whether its next point is the head,if it is, means the node you've already visited,which means the link has a cycle.

这个 roundabout 还是很聪明的; 不过这个是一个带有 transformation 的算法, 一般人确实不怎么敢往这个方向想;

Problem Description

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

Follow up:
Can you solve it without using extra space?

Difficulty:Easy
Total Accepted:183.1K
Total Submissions:517.4K
Contributor: LeetCode
Companies
amazon microsoft bloomberg yahoo
Related Topics
linked list two pointers
Similar Questions
Linked List Cycle II