判断链表中是否有环

//快慢指针能相遇说明有环！
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null)
            return false;
        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;  
    }
}

//遍历链表的同时，让前一个节点的next指向head（或者是任意一个指定的内存），
//在后续的遍历中，如果有节点的当前next指向了head，则说明有环。
//破坏链表，达到最快
public class Solution {
    public boolean hasCycle(ListNode head) {
        ListNode p = head;
        while(p!=null){
            ListNode aft = p.next;
            if(aft==head) return true;
            p.next=head;
            p=aft;
        } 
        return false;
    }
}

https://leetcode.com/problems/linked-list-cycle/

思路1：hash map

开一个哈希表，标记访问过的节点，如果重复访问了某一节点，说明有环。需要额外O(n)的空间复杂度。

C++

class Solution {
public:
    bool hasCycle(ListNode *head) {
        unordered_map<ListNode*, bool> m;
        while (head) {
            if (m.find(head) != m.end()) return true;
            m[head] = true;
            head = head->next;
        }
        return false;
    }
};

思路2：快慢指针

用一快一慢指针，开始两个指针都指向链表头部。慢指针每次向前走一步，快指针每次向前走两步。如果有环，则两个指针最终一定会相遇。这种方法无须额外的空间。

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (!head) return false;
        ListNode *slow = head, *fast = head;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
            if (slow == fast) return true;
        }
        return false;
    }
};

相关: http://ihuafan.com/%E7%AE%97%E6%B3%95/floyds-cycle-finding-algorithm

#include <stdbool.h>
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

/**
 * 
 * @param head ListNode类 
 * @return bool布尔型
 */
bool hasCycle(struct ListNode* head ) {
    // write code here

    int  i = 0;

    while (head && i <= 10000) {
        i++; head = head->next;
    }
    
    if (i > 10000) {
        return  true;
    }

    return  false;
}

class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* p=head;
        int len=0;
        while(p){
            len++;
            p=p->next;
            if(len>10000)return true;
        }
       
        
        return false; 
    }
};

//set,不可插入新内容则有重复，链表为环
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head==NULL)
            return false;
        set<ListNode *> s;
        ListNode *p = head;
        while(p!=NULL)
        {
            if(!s.insert(p).second)//不可插入新内容则有重复，链表为环

            {
                 return true;
            }
            else
                p=p->next; //指向下个节点
        }
        return false;
    }
};

package linkedlist;

import java.util.HashSet;

/**
 * 题目描述:
 * Given a linked list, determine if it has a cycle in it.
 * Follow up:Can you solve it without using extra space?
 * 思路：
 * 1.双指针(最优解) 空间O(1)
 * 2.利用Set的无重复 空间O(n)        
 */
//nowcoder pass
public class Solution {
	
	//nocoder pass
    public boolean hasCycle(ListNode head) {
    	if (head == null) {
    		return false;
    	}
    	ListNode slow = head;
    	ListNode fast = head;
    	
    	//仅用判断fast，因为fast快，无环一定比slow先为null
    	while (fast != null && fast.next != null) {
    		slow = slow.next;
    		fast = fast.next.next;
    		if (fast == slow) {
    			return true;
    		}
    	}
    	return false;
    }
    
    //nowcoder pass
//    public boolean hasCycle2(ListNode head) {
//    	if (head == null) {
//    		return false;
//    	}
//    	HashSet<ListNode> set = new HashSet<ListNode>();
//    	while (head != null) {
//    		if (set.contains(head)) {
//    			return true;
//    		} 
//    		set.add(head);
//    		head = head.next;
//    	}
//    	return false;
//    }
}

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (head ==nullptr || head->next ==nullptr) return false;
        ListNode *slow = head;
        ListNode *fast = head;
        while(slow != nullptr && fast != nullptr && fast ->next != nullptr) {
          slow = slow -> next;
          fast = fast -> next -> next;
          //环内快指针追上了慢指针，设最初（满指针进入环的第一个节点时候）原来快指针和慢指针相距n，每次都会追上一个距离，n-1, n-2,...最终距离为0，也就是相遇
          if (slow == fast) return true;
        }
        return false;
    }
};

function hasCycle( head ) {
    // write code here
    // 有环就会再次遇到
    while (head != null) {
        if (head.val == Infinity) {
            return true;
        } 
        head.val = Infinity;
        head = head.next;
    }
    return false;
}
module.exports = {
    hasCycle : hasCycle
};

function hasCycle( head ) {
    // write code here
    const circleSet = new Set()
    while(head){
        if(circleSet.has(head))
            return true
        circleSet.add(head)
        head = head.next
    }
    return false
    
}
module.exports = {
    hasCycle : hasCycle
};