這題從前校招的時(shí)候看面試寶典的時(shí)候就見到過(guò)。思想就是快慢指針衷恭。
- Use two pointers, walker and runner.
- walker moves step by step. runner moves two steps at time.
- if the Linked List has a cycle walker and runner will meet at some point.
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null) return false;
ListNode walker = head ;
ListNode runner = head ;
while (runner.next !=null && runner.next.next != null){
walker = walker.next ;
runner = runner.next.next ;
if(walker == runner) return true ;
}
return false;
}
}
時(shí)間O(n)，空間O(1)杖狼。
這程序?qū)懫饋?lái)有個(gè)注意點(diǎn)披蕉，就是while語(yǔ)句的判斷，runner.next !=null && runner.next.next != null
這個(gè)條件是值得注意的伞访，首先它是遞進(jìn)的掂骏，先判斷runner.next再判斷runner.next.next；其次它只判斷runner不用判斷walker厚掷，因?yàn)閞unner永遠(yuǎn)走在前面弟灼。我一開始寫成walker.next !=null && runner.next.next != null這種是錯(cuò)的。
O(n)空間的方法
其實(shí)這道題的follow up說(shuō)冒黑，能不能用一個(gè)不需要空間的方法田绑？說(shuō)明除了快慢指針還有其他方法的。搜索了一下抡爹，發(fā)現(xiàn)O(n)空間的方法是：
遍歷鏈表掩驱，如果某個(gè)節(jié)點(diǎn)重復(fù)出現(xiàn)，那就是有環(huán)冬竟。
另外欧穴，對(duì)于有環(huán)我還有一些問題，比如1->2->1->2->3這樣的單鏈表算不算有環(huán)泵殴？等等涮帘。
問了下師弟，師弟說(shuō)我蠢笑诅。2怎么能既指向1又指向3呢调缨？
這題在Java跟C里面有一些不一樣。
這個(gè)O(n)空間的方法的描述應(yīng)該是這樣的：
從鏈表頭開始遍歷整個(gè)鏈表吆你，并且記錄已經(jīng)遍歷過(guò)的結(jié)點(diǎn)地址弦叶，如果發(fā)現(xiàn)有正在遍歷的結(jié)點(diǎn)是已經(jīng)遍歷過(guò)的，則說(shuō)明是存在環(huán)的早处。但是這種方式就需要使用額外的空間來(lái)存放遍歷過(guò)的結(jié)點(diǎn)地址湾蔓。
看清楚了，存放的是結(jié)點(diǎn)地址砌梆，而不是節(jié)點(diǎn)默责。在Java里面贬循，雖然你可以生成同樣value、同樣next的結(jié)點(diǎn)桃序，但是無(wú)法檢查arraylist里面是否已經(jīng)有這個(gè)結(jié)點(diǎn)的「地址」杖虾，不，我想了下媒熊，下面這個(gè)代碼奇适，list.contains檢查的應(yīng)該就是head的地址！：
public static boolean hasCycle(ListNode head) {
if (head == null) return false;
ArrayList<ListNode> list = new ArrayList<>();
while (head != null) {
if (list.contains(head)) {
return true;
}
head = head.next;
list.add(head);
}
return false;
}
test case這樣寫就行了：
ListNode n1 = new ListNode(1);
ListNode n2 = new ListNode(2);
n1.next = n2;
n2.next = n1;
但是上面這個(gè)方法的復(fù)雜度在leetcode中TLE了芦鳍，不知是不是寫的有問題嚷往。復(fù)雜度應(yīng)該跟http://www.reibang.com/p/52f9a3346a88 這個(gè)里面的一樣的。
reference：
http://blog.sina.com.cn/s/blog_725dd1010100tqwp.html
http://www.programcreek.com/wp-content/uploads/2012/12/linked-list-cycle-300x211.png
