LeetCode142. 环形链表 II

题目描述

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改链表。

示例

提交的代码

public class Solution {
    public ListNode detectCycle(ListNode head) {
        return recursionMethod(head);
    }

    public ListNode recursionMethod(ListNode cur){
        if(cur==null)return null;
        if(cur.val==Integer.MIN_VALUE)return cur;
        cur.val=Integer.MIN_VALUE;
        return recursionMethod(cur.next);
    }
}

思想

这里用到了深度遍历无向图中的递归方法：首先要将图中所有节点的标志位置为false，即所有图节点都未遍历过。如果遍历到当前节点，将当前节点的标志位置为true代表已经遍历的节点，当递归遇到节点的标志为true时，则代表当前图中有环。

题目的提示如下

-10^5<=Node.val<=10^5

而Integer.MIN_VALUE为-2147483648，一定超出这个val的界限的，所以方法类似，遍历过的节点就将它的val设置为Integer.MIN_VALUE,代表当前节点已经遍历过了，当递归遇到val值为MIN_VALUE的时候，就代表它是第一个环入口(因为题目中的链表是单向的，不像无向图，所以它一定是环的入口)。
当然了，我这个方法返回的节点中的值已经改变了，但是看着题目描述中系统判断的是链表中的pos，所以就抱着试试看的想法，取巧解决掉了。