[LeetCode]Linked List Cycle

Question Given a linked list, determine if it has a cycle in it.

Follow up: Can you solve it without using extra space?

---

本题难度Easy。有2种算法分别是： 集合法和快慢指针法

1、集合法

【复杂度】 时间 O(N) 空间 O(N)

【思路】 看本节点cur是否在集合内，如果不在就把cur放入集合内，然后考察下一个节点。

【代码】

/** * 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) { //require Set<ListNode> set=new HashSet<>(); ListNode cur=head; //invariant while(cur!=null){ if(set.contains(cur))return true; set.add(cur); cur=cur.next; } //ensure return false; } }

2、快慢指针法

【复杂度】 时间 O(N) 空间 O(1)

【思路】 设两个指针1个快fast1个慢low，如果有环，那么这两个指针必然会在环中某个点相遇。

【代码】

public class Solution { public boolean hasCycle(ListNode head) { //require ListNode low=head,fast=head; //invariant while(fast!=null&&fast.next!=null){ fast=fast.next.next; low=low.next; if(fast==low)return true; } //ensure return false; } }