leetcode 热题 100_环形链表 II

题解一：

        哈希表：遍历链表，用哈希表存储遍历过的链表节点，判断链表节点是否在哈希表中存在，如果存在说明链表出现过，第一个重复出现的节点即为开始入环的第一个节点。

import java.util.HashSet;

public class Solution {
    public ListNode detectCycle(ListNode head) {
        HashSet<ListNode> set = new HashSet<>();
        while (head != null) {
            if (set.contains(head)) return head;
            else set.add(head);
            head = head.next;
        }
        return null;
    }
}

题解二：

        快慢指针：用一快一慢的双指针遍历链表，如果指针不相遇则说明不存在环形结构，如果相遇则存在环形结构。第一次相遇时，快指针走过的路程是慢指针的两倍fast=2*slow，快指针相比慢指针多走了若干圈环形结构fast=slow+n*circle，两式相减会得到slow=n*circle。从链表开始的某个指针要到达环形开始节点处，需要走straight+n*circle步（其中的straight表示进入环形前的一段，n*circle表示在环形走走了若干圈还是回到环形开始节点），所以此时慢指针再走straight步就会到达环形开始节点。同时在此时从链表头出发的新指针也会在straight步后到达环形开始节点，与慢指针相遇。附上过程图解（来源. - 力扣（LeetCode））

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast == slow) {
                ListNode temp = head;
                while (temp != slow) {
                    temp = temp.next;
                    slow = slow.next;
                }
                return temp;
            }
        }

        return null;
    }
}