題目
給定一個(gè)鏈表溃槐，判斷鏈表中是否有環(huán)匣砖，并返回結(jié)果。
原理
遍歷
聲明一個(gè)Set，遍歷鏈表放入Set脆粥，如果放入失敗砌溺，說明有環(huán)。
雙指針
聲明一個(gè)快指針和一個(gè)慢指針变隔，快指針每次移動(dòng)兩步，慢指針移動(dòng)一步蟹倾，如果兩指針相等則說明有環(huán)匣缘。
代碼
遍歷
public static void main(String[] args) {
ListNode listNode5 = new ListNode(5, null);
ListNode listNode4 = new ListNode(4, listNode5);
ListNode listNode3 = new ListNode(3, listNode4);
ListNode listNode2 = new ListNode(2, listNode3);
ListNode listNode1 = new ListNode(1, listNode2);
listNode5.next = listNode2;
System.out.println(hasCircleByFor(listNode1));
}
private static boolean hasCircleByFor(ListNode head) {
Set<ListNode> nodeSet = new HashSet<>();
while (head != null) {
if (!nodeSet.add(head)) {
return true;
}
head = head.next;
}
return false;
}
雙指針
public static void main(String[] args) {
ListNode listNode5 = new ListNode(5, null);
ListNode listNode4 = new ListNode(4, listNode5);
ListNode listNode3 = new ListNode(3, listNode4);
ListNode listNode2 = new ListNode(2, listNode3);
ListNode listNode1 = new ListNode(1, listNode2);
listNode5.next = listNode2;
System.out.println(hasCircleByTwoPointer(listNode1));
}
private static boolean hasCircleByTwoPointer(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;
}
