【算法刷题】链表是否有环且输出入环节点--缓存记录法（JAVA）

【题目】LeetCode 142 linked-list-cycle II（环形链表）

【题址】https://leetcode-cn.com/problems/linked-list-cycle-ii/

【题干】

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。

说明：不允许修改给定的链表。

示例 1：

输入：head = [3,2,0,-4], pos = 1

输出：tail connects to node index 1

解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：
输入：head = [1,2], pos = 0

输出：tail connects to node index 0

解释：链表中有一个环，其尾部连接到第一个节点。
 

示例 3：
输入：head = [1], pos = -1

输出：no cycle

解释：链表中没有环。
【思路】

 遍历一遍链表，每项均添加入缓存set中，判断是否遍历过此节点确定是否有环，若有环返回此节点，若无环返回null

【程序】

	/**
	 * @author 白雪红叶约 2019.05.01 
	 * 【题目】142. linked-list-cycle-ii（链表是否有环,并输出入环节点） 
	 * 【思路】缓存记录法。
	 *         遍历一遍链表，每项均添加入缓存set中，判断是否遍历过此节点确定是否有环，若有环返回此节点，若无环返回null
	 * 【时间复杂度】O(n) 
	 * 【空间复杂度】O(n)
	 * @param head 原始链表头结点
	 * @return <ListNode> 入环节点或null
	 */
	public ListNode detectCycle2(ListNode head) {
		Set<ListNode> cacheSet = new HashSet<ListNode>();
		while (!cacheSet.contains(head)) {
			if (head == null)
				return null;
			cacheSet.add(head);
			head = head.next;
		}
		return head;
	}

【图解】

以 head = [1,2,3,4,5,6], pos = 3为例

（0）初始化缓存空间（set）

Set<ListNode> cacheSet = new HashSet<ListNode>();

（1-6）逐个遍历节点，并判断是否遍历过，若没遍历过则将其加入缓存

（7）遍历节点，发现若之前遍历过，则直接返回结果