序
本文次要记录一下leetcode链表之环路检测
题目
给定一个链表，如果它是有环链表，实现一个算法返回环路的结尾节点。有环链表的定义：在链表中某个节点的next元素指向在它后面呈现过的节点，则表明该链表存在环路。 示例 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解释：链表中没有环。 进阶：你是否能够不必额定空间解决此题？起源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/linked-list-cycle-lcci著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。题解
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */public class Solution { public ListNode detectCycle(ListNode head) { ListNode slow = head; ListNode fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { break; } } if (fast == null || fast.next == null) { return null; } while (head != fast) { head = head.next; fast = fast.next; } return head; }}小结
借助额定空间的话，应用HashSet，遍历链表直到游标指针为null或者找到HashSet中存在的元素；如果不借助额定空间的话，先用快慢指针遍历找到相交的节点，若没有相交的节点间接返回，若有相交的节点，则再次从头遍历，同时挪动头指针与快慢指针相遇的节点指针，若二者相遇则找到入口节点。
doc
- 环路检测