判断是否含有环状子链表

2020-07-20

本文将提供两种解法：哈希表和双指针(快慢指针)
1.哈希表解法:我们将已经遍历过的节点加入到Set集合中，然后判断如果遍历的当前节点在集合中已存在，那么就是有环状结构，如果没有，将一直遍历到链表尾部，需要用额外的空间来辅助:

public boolean hasCycle(ListNode head) {
    Set<ListNode> nodesSeen = new HashSet<>();
    while (head != null) {
        if (nodesSeen.contains(head)) {
            return true;
        } else {
            nodesSeen.add(head);
        }
        head = head.next;
    }
    return false;
}

2.利用双指针，利用fast和slow两个指针，可以想象成两个运动员在环形赛道上奔跑，fast在slow前方，那么总有一个时刻，fast会再次与slow相遇，我们就是采取这种想法

public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head==null||head.next==null) {
			return false;
		}
		ListNode slow = head;
		ListNode fast = head.next;
		while(slow!=fast) {
		    //如果fast能到达尾部，则不存在环，由于我们一次走两步，所以为了防止空指针，要判断两个位置
			if(fast==null||fast.next==null) {
				return false;
			}
			slow = slow.next;
			fast = fast.next.next;
		}
		return true;
	}

}