141. Linked List Cycle

Leetcode Linked List

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

Follow up:

Can you solve it without using extra space?

分析

判断链表是否有环。这里使用两种方案：

1. 第一种当然最直接，把元素放到hashset中，然后看该元素是否已经包含在hashset中。
2. 第二种，需要动一点脑子，
   • 两个指针，一直跑，一前一后，前面的跑的快，后面的跑得慢，看快的是否能追上慢的。
   • 追的上，说明链表肯定是有循环的。如果跑的快的直接跑到终点了，那就是没循环。

/**
 *  Use the method of HashSet
 *  To detect if a list is cyclic,
 *  we can check whether a node had been visited before.
 *   A natural way is to use a hash table.
 */
public boolean hasCycle(ListNode head) {
    HashSet<ListNode> set = new HashSet<>();
    while (head != null) {
        if (set.contains(head)) {
            return true;
        }
        set.add(head);
        head = head.next;
    }
    return false;
}

两个指针的方案，想象一下两个运动员在跑道上以不同的速度跑步。如果跑道是个圆，那么将会发生什么？考虑两个不同速度移动的指针 - 慢指针和快指针。如果在链表中没有环，快指针将会跑到终点，我们可以返回false。如果链表中包含环，那么快指针和慢指针最终将相遇。

• 注意要让fast跑在slow前面，这样才能跑完完整一圈

public boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) return false;
    ListNode slow = head;   // 慢指针在后
    ListNode fast = head.next;  // 快指针在前

    while (fast != slow) {  // 判断是否相遇
        // 快指针跑完了，返回false
        if ((fast == null) || (fast.next == null)) return false; 
        slow = slow.next;
        fast = fast.next.next;
    }
    return true;
}

• 也可以让慢指针和快指针同时从起点开始，但是while循环判断的条件要改变，因为一开始fast = slow.

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