判断链表中是否有环

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 cycle = head;
        return hasCycle1(head, cycle.next,1);
    }

    public static boolean hasCycle1(ListNode headNext, ListNode cycleNode, int k) {
        if (headNext == null || cycleNode == null){
            return false;
        }
        ListNode headFirst = headNext;
        boolean flag = false;
        int i = 1;
        while (i <= k && headNext.next != null){
            if (i != 1 && headFirst == cycleNode){
                flag = true;
                break;
            }
            headFirst = headFirst.next;
            i++;
        }
        if (!flag){
            flag = hasCycle1(headNext, cycleNode.next, k+1);
        }
        return flag;
    }
}
解题思路：这个方法就是我首先假设环节点cycle是头结点head的下一个节点，
此时令k=1，表明我接下来只需要比对头结点head和环节点cycle，如果它们相等的话就表明头结点就是环节点，
不是的话令k+1，环节点cycle = cycle.next再进行遍历，
根据环链表的特性，遍历到最后肯定是会存在环节点和链表中的某个节点是相等的，为什么要引入k，是为了防止程序陷入死循环，k小了可能会遍历不到环节点，所以，每次就以k+1来进行递归，这样一来如果链表存在环，则一定会被有遍历到的时候

我用的 do while

public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode quick,slow;
        if(head == null){
            return false;
        }
        quick = head;
        slow = head;

        do{
            if(slow == null || quick == null || quick.next == null){
                return false;
            }
            slow = slow.next;
            quick = quick.next.next;
        }while(quick != slow);
        return true;
    }
}

破坏性查找最快
public boolean hasCycle(ListNode head) {
         ListNode const_tail = new ListNode(999);
         while(head != null){
            if(head.next == head) return true;
            if(head.next == const_tail)  return true;
            ListNode temp =  head;
            head = head.next;
            temp.next = const_tail;
         }
         return false;
    }

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) {
        // 左程云老师讲过类似的题，那道题是这道题的进阶问题，要求返回成环的结点
        // 采用快慢指针，快指针一次走两个结点，慢指针一次走一个结点，若二者能相遇，则有环，否则无环

        // 补充：若要求返回成环（相交）结点，那么在快慢指针相遇之后，令快指针返回head，降速成一次走一个结点
        // 当二者再次相遇的结点就是成环结点

        // 算法的时间复杂度O(N)，额外空间复杂度O(1)

        // 1.先判断链表为空的情况
        if (head == null) {
            return false;
        }
        // 2.确定链表不为空
        ListNode fast = head;
        ListNode slow = head;

        do {
            // 3.如果链表是无环的，那么fast一定先走到null，直接return false即可
            if (fast.next == null || fast.next.next == null) {
                // 这里一定不会报空指针异常，因为先判断fast.next == null，若满足，则直接return false，不会继续判断后面
                return false;
            }
            // 4.快指针一次走两个结点，慢指针一次走一个结点
            fast = fast.next.next;
            slow = slow.next;
        } while(fast != slow);
        // 5.若因为fast == slow而结束循环，说明fast和slow二者相遇了，说明链表有环
        return true;
    }
}

public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null) {
            return false;
        }
        if (head.val == 100001) {
            return true;
        }
        head.val = 100001;
        return hasCycle(head.next);
    }

//循环超过10000次说明有环
public class Solution {
    public boolean hasCycle(ListNode head) {
        int count=1;
        while(head!=null)
        {
            head=head.next;
            count++;
            if(count>10000)
                return true;
        }
        return false;
    }
}

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) {
        ListNode fast=head;
        ListNode slow=head;
        if(head==null){
            return false;
        }
        while(fast!=null&&fast.next!=null){  //如果没环的话快指针会先到链表尾
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                return true;
            }
        }
        return false;
    }
}

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String input = null;
        while ((input = br.readLine()) != null) {
            String[] ss = input.split("}");
            int last = Integer.parseInt(ss[1].split(",")[1]);
            System.out.println(last != -1);
        }
    }
}

public boolean hasCycle(ListNode head) {
    if (head == null) return false;
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast)
            return true;
    }
    return false;
}

public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null){
            return false;
        }
        List<ListNode> list = new ArrayList<>();
        while(head != null){
            if(list.contains(head)){
                return true;
            }
            list.add(head);
            head = head.next;
        }
        return false;
    }

public boolean hasCycle(ListNode head) {
        //找环，快慢指针  终将相遇
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                return true;
            }
        }
        return false;
    }