面试题 02.08. 环路检测

解题思路

1.分析题意，是判断节点相等，而不是节点的值相等
2.对于链表进行遍历，用一个数据结构保存遍历到的节点
3.判断遍历到的节点是否在保存的列表中，如果在，则return 这个节点
4.如果链表遍历到末尾（next为空），则链表不存在环

解题遇到的问题

无

后续需要总结学习的知识点

1.用数组或者List保存遍历到的节点，都是使用了存储空间，是否可以不用额外空间解决此题？

##解法
class Solution {
    public ListNode detectCycle(ListNode head) {
        List<ListNode> list = new ArrayList<ListNode>();
        while (head != null) {
            if (list.contains(head)) {
                return head;
            } else {
                list.add(head);
            }
            head = head.next;
        }
        return null;
    }

    public class ListNode {
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
        }
    }
}