3月2日 Linked List Cycle

今天星期天，准備好周一的PPT內容，再回來做題，以後考慮周末做一個APP或者微信帳號玩吧。

回到題目， Linked List Cycle，一個檢查單項鏈表是否有環路的問題。

題目周五的時候就簡單做過，可是鏈表中帶入了一個val常量，當時誤以為是要檢查是否有重復值，WA了。

早上再試了會，緩過來，其實還是比較地址指針。

最開始寫的一個簡單方法，只能判斷是否與頭指針重復，但是如果環路從中間開始就判斷不到了，再想了10多分鐘，有一個O(n^2)的算法，每次從第一個指針開始，判斷後面k-1個指針是否相同：

 hasCycle(ListNode * (head == NULL)   (head->next == NULL)  
*p = head-> counter =  (p !=
            ListNode *cpr = ( i = ; i < counter; ++ (cpr == p)  = cpr->= p->++ 

可惜，TLE超時了，看了下用例，最大長度已經超過5000，5000的平方已經超過2千5百萬，確實是超過1秒了。

後續又思考了半個多小時，畫滿了一張草稿紙也沒想好，囧，戰斗力下滑啊。

看了Discuss裡，一句話就明白了，一個跑得快，一個跑得慢，兩個相遇的時候就是環路了。

所以就有了下面的做法，寫的比較快，所以加了if多一點：

 hasCycle(ListNode * (head == NULL)   (head->next == NULL)   (head->next->next == NULL)  *p = head->*p2 = head->next-> (p != NULL && p2 != (p == p2)   (p2->next == NULL)   (p2->next->next == NULL)  = p->= p2->next-> 

下次遇到類似的問題，考慮從反方向思考。