判断链表中是否有环

破坏性查找最快
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;
    }

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 || head.next == null) {
            return false;
        }
        if (head.val == 100001) {
            return true;
        }
        head.val = 100001;
        return hasCycle(head.next);
    }
}

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; } slow = slow.next; fast = fast.next.next; }
    return true; }

其中，ListNode是链表节点的定义，包含一个val属性和一个next属性，表示节点的值和下一个节点的指针。具体代码实现中，我们使用快慢指针的方法来判断链表是否有环。我们让一个指针slow每次移动一步，另一个指针fast每次移动两步，如果链表有环，那么fast指针最终会追上slow指针，从而形成一个循环。如果fast指针走到了链表的末尾，那么说明链表没有环。

public class Solution {
    public boolean hasCycle(ListNode head) {
        int x = (int)1e5+1;
        while ( head != null ) {
            if ( head.val == x ) return true;
            head.val = x;
            head = head.next;
        }
        return false;
    }
}

public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null||head.next==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;
    }
}