題目地址：https://leetcode-cn.com/problems/linked-list-cycle/
題目：
給定一個(gè)鏈表，判斷鏈表中是否有環(huán)。
進(jìn)階：你能否不使用額外空間解決此題？
試題分析：
查看鏈表是否有環(huán)主要有兩個(gè)方法比較，
一種是利用set數(shù)據(jù)結(jié)構(gòu)，set是一種不會(huì)有重復(fù)數(shù)據(jù)的集合結(jié)構(gòu)，遍歷鏈表，將鏈表的節(jié)點(diǎn)依次放入set中，如果遍歷的節(jié)點(diǎn)在set中還沒(méi)有則add到set中，如果已經(jīng)存在則說(shuō)明鏈表有重復(fù)節(jié)點(diǎn)有環(huán)。
還有一種方法是比較特殊的算法，快慢指針?lè)ǎ@種算法比較詭異，一般人不容易想到，核心思路就是定義兩個(gè)指針，一個(gè)快指針、一個(gè)慢指針，慢指針每次只移動(dòng)一個(gè)節(jié)點(diǎn)，快指針每次移動(dòng)兩個(gè)節(jié)點(diǎn)，如果整個(gè)鏈表中有環(huán)，那么快慢指針一定會(huì)相遇，不相信的話，可以自己在草稿紙上分步畫(huà)下就會(huì)發(fā)現(xiàn)如果有環(huán)一定會(huì)相遇。
代碼：
<pre class="md-fences md-end-block" lang="java" contenteditable="false" cid="n89" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: Consolas, "Liberation Mono", Courier, monospace; font-size: 0.9em; white-space: pre; text-align: left; break-inside: avoid; display: block; background-image: inherit; background-size: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(221, 221, 221); border-top-left-radius: 3px; border-top-right-radius: 3px; border-bottom-right-radius: 3px; border-bottom-left-radius: 3px; padding: 8px 1em 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; caret-color: rgb(51, 51, 51); color: rgb(51, 51, 51); font-style: normal; font-variant-caps: normal; font-weight: normal; letter-spacing: normal; orphans: auto; text-indent: 0px; text-transform: none; widows: auto; word-spacing: 0px; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; text-decoration: none; background-position: inherit inherit; background-repeat: inherit inherit;"> public boolean hasCycle(ListNode head) {
HashSet<ListNode> set = new HashSet<ListNode>();
while(head!=null){
if(set.contains(head)){
return true;
}else{
set.add(head);
head = head.next;
}
}
return false;
}
?
public boolean hasCycle2(ListNode head) {
//快慢指針?lè)椒?，快指針比慢指針每次快兩?br>
ListNode slow =head;
ListNode fast = head;
while(slow!=null && fast!=null && fast.next!=null){
slow = slow.next;
fast = fast.next.next;
if(slow==fast){
return true;
}
}
return false;
}</pre>
源碼路徑：com.monkey01.linkedlist.LinkedListCycle_141
配套測(cè)試代碼路徑：test目錄com.monkey01.linkedlist.LinkedListCycle_141Test
