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

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) {

        if (head == null) {
            return false;
        }
        ListNode  a = head;
        ListNode  b = head;

        while (a != null) {

            if (a.next == null) {
                return false;
            }
            a = a.next.next;
            b = b.next;
            if (a == b) {
                return true;
            }

        }


        return false;
    }
    // public boolean hasCycle(ListNode head) {

    //     HashSet<ListNode> set = new HashSet<>();
    //     if (null == head) {
    //         return false;
    //     }

    //     return handData(set, head);
    // }


    // public boolean handData(   HashSet<ListNode> set, ListNode head) {

    //     if ( head.next == null ) {
    //         return false;
    //     }
    //     if (set.contains(head)) {
    //         return true;
    //     }
    //     set.add(head);
    //     return handData(set, head.next);
    // }
}

思路：两种解法

1. 使用空间换时间， 降所有遍历的节点存起来，发现重复时，未有环
2. 使用快慢指针，当两指针相遇时说明 有环