[問題] LeetCode的題目

作者: p31819 (凜大小姐~最高!!)   2017-11-26 20:57:26
大家好,小弟是個初學者。
最近在 LeetCode練習JAVA
今天寫到一題感覺應該沒問題的,但卻過不了。
想請問有什麼問題
題目是LeetCode的第141題
網址 https://leetcode.com/problems/linked-list-cycle/description/
這題是要檢查Linked List是不是個循環List
我寫的CODE是這樣的:
public static boolean hasCycle(ListNode head) {
if (head == null || head.next == null)
return false;
boolean ans = false;
ListNode next = head.next;
while (next != null) {
if (next == head)
return true;
else
next = next.next;
}
return ans;
}
想法是直接比對物件的位址,
如果是循環的,會接回第一個點。
我自己在電腦上測是沒問題。
可是LeetCode給我 Time Limit Exceeded 判定
Last executed input:
[3,2,0,-4]
tail connects to node index 1
這CASE我自己跑好像不到1ms
不知道為什麼會是TLE
不知道有沒有大大可以幫我看一下?
謝謝!
作者: pipi99 (I think so I am)   2017-11-26 21:27:00
他是跟你說 因為-4其實連結到第一個節點2了依照你的程式碼while那段會無窮迴圈,因為-4會接回2
作者: p31819 (凜大小姐~最高!!)   2017-11-26 22:49:00
喔喔 原來是跳過第一個的循環,我一直以為index1是第一個.
作者: cha122977 (CHA)   2017-11-29 19:27:00
不過你誤會cycle的意思了,不一定是接回頭,可以接身體
作者: fayhong (恰似飛鴻踏雪泥)   2017-11-30 06:16:00
我猜用一個類似 bubble sort 的迴圈,檢查是否有任兩個節點的 next 是相等的就好了,空間代價 0,時間成本 n^2
作者: wawi2 (@@)   2017-11-30 09:15:00
這題不是用兩個指標slow跟fast比較就好了嗎? 線性時間
作者: s06i06 (三條魚)   2017-11-30 10:58:00
龜兔賽跑演算法
作者: p31819 (凜大小姐~最高!!)   2017-11-30 15:38:00
感謝大家,後來的確是用兩個指標讓他跑。一開始以為cycle都會接回頭,所以想說用一個跑就好
作者: cha122977 (CHA)   2017-12-01 01:56:00
btw 這題沒做過真的很難想到不用空間的線性解...

Links booklink

Contact Us: admin [ a t ] ucptt.com