給定一個(gè)鏈表，判斷鏈表中是否有環(huán)
如果鏈表中有某個(gè)節(jié)點(diǎn)，可以通過連續(xù)跟蹤 next 指針再次到達(dá)绍在，則鏈表中存在環(huán)。 為了表示給定鏈表中的環(huán)雹有，我們使用整數(shù) pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）偿渡。 如果 pos 是 -1，則在該鏈表中沒有環(huán)霸奕。注意：pos 不作為參數(shù)進(jìn)行傳遞溜宽，僅僅是為了標(biāo)識(shí)鏈表的實(shí)際情況。
如果鏈表中存在環(huán)质帅，則返回 true 适揉。 否則，返回 false 煤惩。
示例1：
1-->2
2-->1輸入：head = [1,2], pos = 0
輸出：true
解釋：鏈表中有一個(gè)環(huán)嫉嘀，其尾部連接到第一個(gè)節(jié)點(diǎn)。
示例2：
3-->2 -->0-->-4
-4-->2輸入：head = [3,2,0,-4], pos = 1
輸出：true
解釋：鏈表中有一個(gè)環(huán)魄揉，其尾部連接到第二個(gè)節(jié)點(diǎn)剪侮。
示例3：
1
輸入：head = [1], pos = -1
輸出：false
解釋：鏈表中沒有環(huán)。
提示：
鏈表中節(jié)點(diǎn)的數(shù)目范圍是 [0, 104]
-105 <= Node.val <= 105
pos 為 -1 或者鏈表中的一個(gè) 有效索引 什猖。
Java解法
思路：
- 最簡(jiǎn)單的做法票彪，是遍歷鏈表時(shí)，將經(jīng)過的位置記錄不狮，一旦重復(fù)降铸，跳出給出位置即可
- 節(jié)省空間的辦法是利用雙指針中的快慢指針判斷重合（新的利用，參考官方解摇零，效率更高）
package sj.shimmer.algorithm.m4_2021;
import java.util.HashMap;
import sj.shimmer.algorithm.ListNode;
/**
* Created by SJ on 2021/4/9.
*/
class D72 {
public static void main(String[] args) {
ListNode node = ListNode.createNode(new int[]{3, 2, 0, -4});
node.next.next.next = node.next;
System.out.println(hasCycle(node));
ListNode node2 = ListNode.createNode(new int[]{1});
System.out.println(hasCycle(node2));
}
public static boolean hasCycle(ListNode head) {
HashMap<ListNode, Integer> map = new HashMap<>();
ListNode next = head;
map.put(head, 0);
int pos = 0;
while (next.next != null) {
pos++;
Integer integer = map.getOrDefault(next.next, -1);
if (integer != -1) {
return true;
}
map.put(next.next, pos);
next = next.next;
}
return false;
}
public static boolean hasCycle2(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;
}
}
image
image
官方解
-
快慢指針
上方解法2
時(shí)間復(fù)雜度：O(N)
空間復(fù)雜度：O(1)
