題目描述
141.環形鏈表
給定一個鏈表，判斷鏈表中是否有環，
為了表示給定鏈表中的環，我們使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）， 如果 pos 是 -1，則在該鏈表中沒有環，
示例 1：
輸入：head = [3,2,0,-4], pos = 1
輸出：true
解釋：鏈表中有一個環，其尾部連接到第二個節點，
示例 2：
輸入：head = [1,2], pos = 0
輸出：true
解釋：鏈表中有一個環，其尾部連接到第一個節點，
題目決議
方法一：哈希表
解題思路
首先可以想到的方法就是遍歷鏈表并將遍歷的鏈表Node節點存入哈希表中，通過哈希表是判斷Node是否已經存在，若已經存在則說明鏈表存在環，否則無環，
代碼示例
Java：
/*
* Definition for singly-linked list.
*/
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public boolean hasCycle(ListNode head) {
Set<ListNode> visited = new HashSet<ListNode>();
ListNode curr = head;
while (curr != null) {
if (visited.contains(curr)) {
return true;
}
visited.add(curr);
curr = curr.next;
}
return false;
}
復雜度分析
時間復雜度：O(n)
空間復雜度：O(n)，通過額外空間存盤遍歷節點
方法二：雙指標
解題思路
假設鏈表存在環，若兩個遍歷速率不一樣的指標同時遍歷整個鏈表，這兩個指標最侄訓相遇，所以我們可以采用 快慢指標 的方式將空間復雜度優化到O(1)，慢指標slow每次遍歷一個節點，快指標fast每次遍歷兩個節點，直到指標走到鏈表末尾或者兩個指標相遇，
代碼示例
Java：
/*
* Definition for singly-linked list.
*/
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
public boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while(fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return true;
}
}
return false;
}
復雜度分析
時間復雜度：O(n)
空間復雜度：O(1)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/65509.html
標籤：其他