141.環形鏈表

法一：快慢指針

思路：

用兩個指針slow,fast,后者能比前者多走一步路，那判斷是不是有環，只需要判斷是否會相遇。

就是有一個能比烏龜跑2倍快的兔子，兩小只都在有環的路上跑，那是不是肯定會相遇。

嗯，對！

代碼：

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
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;}
}

法二：哈希表

思路：

就是把之前走過的路標記一下，這里可以用哈希表set，set集合中是不允許有重復元素的。然后當重復結點出現的時候,就說明有環了。代碼如下：

代碼：

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public boolean hasCycle(ListNode head) {Set<ListNode> seen=new HashSet<ListNode>();while(head!=null){if(!seen.add(head)){return true;}head=head.next;}return false;}
}

142.環形鏈表II

?這道題可以借鑒141.環形鏈表的解法，不過是用哈希表的沒多少改動，但是用快慢指針的話那就需要額外注意了。

在這里的話我犯了一個錯誤，用快慢指針法的時候我認為兩指針相遇的結點就是該鏈表開始入環的第一個節點。還有就是當head=[-1, -7, 7, -4, 19, 6, -9, -5, -2, -5] ,p=9時就錯誤的認為兩個-5就是相同的。

題解：

設一個情景，方便理解。有個烏龜和兔子，兔子腿長，當然就跑的比較快，這里我規定其速度為烏龜的兩倍。它倆在一個有環的地方相遇。看下圖，紅點的地方是相遇點，然后我們可以得出烏龜走的路是X+Y，兔子的是X+Y+N*(Y+Z)，這個能看懂吧，然后兩者的關系是2*(X+Y)=X+Y+N*(Y+Z)，因為速度是2倍關系。然后化簡最后就是X=(n-1)(Y+Z)+Z。好，這里的話。我們這樣來理解。當n等于1時，X=Z，意味著只要用個命運之手將爬到相遇點的烏龜放到原點（多多少少有點殘忍），然后再將兔子限速為烏龜的速度，這樣二者必將會在目的點相遇，這個時候我們只需要返回即可。那么當n>1時，那也沒關系，這就說明x的確實有點長，兔子只需要繼續保持著龜速前進即可。圖有點丑，見諒見諒！

?代碼如下啦：

（參考官方）

碼一：快慢指針

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {if(head==null) return null;ListNode slow=head,fast=head;while(fast!=null){slow=slow.next;if(fast.next!=null){fast=fast.next.next;}else{return null;}if(fast==slow){ListNode ptr=head;while(ptr!=slow){ptr=ptr.next;slow=slow.next;}return ptr;}}return null;}
}

碼二：哈希表

/*** Definition for singly-linked list.* class ListNode {*     int val;*     ListNode next;*     ListNode(int x) {*         val = x;*         next = null;*     }* }*/
public class Solution {public ListNode detectCycle(ListNode head) {Set<ListNode> seen=new HashSet<ListNode>();while(head!=null){if(!seen.add(head)){return head;}head=head.next;}return null;}
}

其實還挺簡單的，主要就是要理解！

好了，刷題快樂喲~