1. 题目:
判断给定的链表中是否有环。如果有环则返回true,否则返回false。
1.1 思路1: 双指针
我们使用两个指针,fast 与 slow。
它们起始都位于链表的头部。随后,slow 指针每次向后移动一个位置,而fast 指针向后移动两个位置。如果链表中存在环,则 fast 指针最终将再次与 slow 指针在环中相遇。
public boolean hasCycle(ListNode head) {
//思路, 设定两个指针,一个指针每次走2步,表示快指针;另外一个指针走一步,表示慢指针;如果存在闭环,则两个指针必然会再次相遇
if (head == null) {
return false;
}
ListNode slow = head;
ListNode fast = head;
while (slow != null && fast != null) {
slow = slow.next;
if (fast.next != null) {
fast = fast.next.next;
} else {
return false;
}
if (slow == fast) {
return true;
}
}
return false;
}
1.2 思路2:哈希表
我们遍历链表中的每个节点,并将它记录下来;一旦遇到了此前遍历过的节点,就可以判定链表中存在环。借助哈希表可以很方便地实现
1、遍历链表,并将访问过的结点存储到哈希表中
2、判断结点是否在哈希表中,若存在则返回 true
3、遍历结束,则返回 false
public boolean hasCycle(ListNode head) {
if (head == null) {
return false;
}
Set<ListNode> sets = new HashSet<>();
while (head != null) {
if (sets.contains(head)) {
return true;
} else {
sets.add(head);
}
head = head.next;
}
return false;
}