141. 環(huán)形鏈表
給定一個(gè)鏈表，判斷鏈表中是否有環(huán)。
為了表示給定鏈表中的環(huán)，我們使用整數(shù) pos 來(lái)表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1坊夫，則在該鏈表中沒有環(huán)。
示例:
輸入：head = [3,2,0,-4], pos = 1
輸出：true
解釋：鏈表中有一個(gè)環(huán)撤卢，其尾部連接到第二個(gè)節(jié)點(diǎn)环凿。
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public boolean hasCycle(ListNode head) {
if(head == null)
return false;
if(head.next == head)
return true;
ListNode preNode = head;
while(preNode != null){
if(preNode.next == null)
return false;
head = head.next;
preNode = preNode.next.next;
if(head == preNode)
return true;
}
return false;
}
}
復(fù)雜度分析
時(shí)間復(fù)雜度 : O(n)
空間復(fù)雜度 : O(1)
