LeetCode题解：环形链表

题目描述

给你一个链表的头节点head，判断链表是否有环。
如果链表中有某个节点，可以通过连接跟踪next指针再次到达，则链表中存在环。为了表示给定链表中的环，评测系统内部使用整数pos来表示链表尾连接到链表中的位置 （索引从0开始）。注意：pos不作为参数进行传递。仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回true。否则，返回false。

示例

• 示例1

  
  示例1

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

• 示例
  输入：head = [1], pos = -1
  输出：false
  解释：链表中没有环。

思路方法

哈希解法

最容易想到的是遍历所有节点，每次遍历到一个节点时，判断该节点此前是否被访问过。
具体的，我们可以使用哈希表来存储所有已经访问过的节点。每次我们到达一个节点，如果该节点已经存在于哈希表中，则说明该链表是环形链表，否则就将该节点加入哈希表中。重复这一过程，知道我们遍历完整个链表即可。

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

复杂度分析：

• 时间复杂度：O(N)。
• 空间复杂度：O(N)，主要为哈希表的开销。

双指针法

还有种方法需要我们观察环形链表的特点。
使用双指针，快指针fast的移动速度远大于慢指针slow的移动速度（在算法中的体现就是，每次移动的距离比慢指针多一个节点）。如果是环形链表，那么快指针一定会追上慢指针，此时就可以判定是否为环形链表。

/**
 * 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||head.next==null){
            return false;
        }
        ListNode slow = head;
        ListNode fast = head.next;
        while(slow!=fast){
             if(fast==null||fast.next==null){
                return false;
            }
            fast = fast.next.next;
            slow = slow.next;
        }
        return true;
    }
}

复杂度分析

• 时间复杂度：O(N)。
• 空间复杂度：O(1)，只需要两个指针的额外开销。