《链表篇》---环形链表

题目传送门 

方法一：哈希表

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

方法二：快慢指针

1.如果没有节点或只有一个节点，返回false。

2.定义一个快指针，一个慢指针。在快指针不等于慢指针的情况下，慢指针走一步，快指针走两步。

3.若快指针走到了最后一个节点，或者最后的空节点。说明没有环，返回false。

4.若有环，则快指针必定会被慢指针追上。因此若相等则返回true。

public class Solution {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;}
}