题解 | 判断链表中是否有环

判断一个链表有没有环：

方法一：判读是否存在入度大于 1 的节点，使用一个哈希表 map 存储每个节点遍历的次数count（以节点的hashCode为key），如果存在 count > 1 的情况就返回 true，否则返回 false。该方法空间复杂度为 O(n)，不合题意

方法二：快慢指针法，设两个同时存在的快慢指针，快指针走2步，慢指针走1步，如果存在环，那么快慢指针总会相遇

import java.util.*;
/**
 * 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) {
        return hasCycleByFastSlowPointer(head);
    }

    /**
     * 快慢指针法
     */
    public static boolean hasCycleByFastSlowPointer(ListNode head) {
        // 使用两个快慢指针，快的走2步，慢的走1步，如果指针相遇，就说明链表有环
        if(head == null) return false;

        ListNode fast = head.next, slow = head;
        while(fast != null && fast.next != null) {	// 保证快指针能走2步，否则说明到表尾或者倒数第二个节点
            if(fast == slow) return true;

            fast = fast.next.next;
            slow = slow.next;
        }
        return false;
    }

    /**
     * 哈希
     */
    public static boolean hasCycleByHash(ListNode head) {
        // 使用一个 Map 记录每个节点的入度
        // 入度：即next指针指向该节点的次数
        Map<Integer, Integer> map = new HashMap<>();
        // 头节点没有入度
        if (head != null) map.put(head.hashCode(), 0);
        while (head != null) {  // 处理NPE
            head = head.next;
            if (head != null) { // 处理NPE
                int code = head.hashCode();
                if (map.getOrDefault(code, 0) > 1) return true;
                map.put(head.hashCode(), map.getOrDefault(code, 0) + 1);
            }
        }

        return false;
    }
}