141. Linked List Cycle

Sol #1:
更改ListNode的结构，加入boolean visited
如果被访问过就置true

Sol #2：
HashSet   O(n) time complexity & O(n) space complexity
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public boolean hasCycle(ListNode head) {
if (head == null) {
return false;
}
Set<ListNode> visited = new HashSet<>();
while (head != null) {
if (visited.contains(head)) return true;
visited.add(head);
head = head.next;
}
return false;
    }
}


Sol #3:
三刷
100.00 %
public class Solution {
    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 (slow == fast) {
                break;
            }
        }
        return fast != null && fast.next != null;
    }
}

slow fast pointers
O(n) time complexity & O(1) space complexity

public class Solution {

   public boolean hasCycle(ListNode head) {

if (head == null || head.next == null) {

return false;

}

ListNode slow = head;

ListNode fast = head;

while (fast != null && fast.next.next != null) {

slow = slow.next;

fast = fast.next.next;

if (slow == fast) {

return true;

}

}

return false;

   }

}

Version #3: 二刷Updated Version

public class Solution {
    /**
     * @param head: The first node of linked list.
     * @return: True if it has a cycle, or false
     */
    public boolean hasCycle(ListNode head) {
        // write your code here
        if (head == null) return false;
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) return true;
        }
        return false;
    }

}