leetcode 巧妙解法之連結清單 141 環形連結清單

給定一個連結清單，判斷連結清單中是否有環。

為了表示給定連結清單中的環，我們使用整數 pos 來表示連結清單尾連接配接到連結清單中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該連結清單中沒有環。

示例 1：

輸入：head = [3,2,0,-4], pos = 1

輸出：true

解釋：連結清單中有一個環，其尾部連接配接到第二個節點。

示例 2：

輸入：head = [1,2], pos = 0

輸出：true

解釋：連結清單中有一個環，其尾部連接配接到第一個節點。

示例 3：

輸入：head = [1], pos = -1

輸出：false

解釋：連結清單中沒有環。

public class Solution {
  public boolean hasCycle(ListNode head) {
   if(head==null||head.next==null)
   {
       return false;
   }
   ListNode p=head;
   ListNode q=head.next;
   while(p!=q)
   {
    if(q==null||q.next==null)
    {
    return false;
    }
    p=p.next;
    q=q.next.next;
    }
   return true;
   }
}
           

使用快慢指針，慢指針每次前進1格，快指指着前進2格，有環的話一定會相遇。

時間複雜度o(n), 空間複雜度 o(1)