leetcode 141. Linked List Cycle

2017-08-04

题意

链表中是否存在环路。

可以做到不用额外的空间做到嘛。

我的思路

可以把节点放到哈希表中，没次遍历的时候去哈希表中去查，如果存在就表示存在循环列表。(当然放ArrayList中也会不会超时)

我的代码

用到了额外的空间。(⊙o⊙)…

public class Solution {
    public boolean hasCycle(ListNode head) {
        Set<ListNode> set = new HashSet<ListNode>();
        while(head!=null){
            if(!set.contains(head)){
                set.add(head);   
            }else{
                return true;
            }
            head = head.next;
        }
        return false;
    }
}

大神代码

假定有两个跑步者在链条上跑步，如果一个跑一下跑一步，一个一下跑两步。
如果存在循环，两者肯定会相遇。想想为什么？

假设两个跑步者都在循环上，他两之间相差距离顶多是循环圈的距离，假定为K，K是小于等于n的。他们的速度差是1，那就是表明顶多k次后他们会相遇。

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