141. 环形链表：十分简单的问题，递归 和 快慢指针 两种方法解决.md

题目简述：

给你一个链表的头节点 head ，判断链表中是否有环。

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

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

题目链接：141. 环形链表

方法一：递归

话不多说，看代码吧，就是利用节点的 val 字段可变但题目本身与 val 无关的特点，通过原地修改 val 标记节点是否已被访问，做到不花费任何额外内存。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

 
public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null || head.next == null) return false;
        head.val = Integer.MIN_VALUE;
        if (head.next.val == Integer.MIN_VALUE) return true;
        return hasCycle(head.next);
    }
}

方法二：双指针（快慢指针）

如果给定的链表没有 val 属性或者不允许我们修改 val 该怎么办呢？这时就可以通过双指针解决。更准确地说是快慢指针，快指针每次递增2，慢指针每次递增1，如果快指针追上了慢指针，就说明存在环路；如果快指针撞到了null，说明不存在环路。

双指针是链表/数组相关问题很常用的方法。代码逻辑也很简单，这里就不多解释了。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */


public class Solution {
    public boolean hasCycle(ListNode head) {
        if (head == null) return false;
        if (head.next == null) return false;
        if (head.next.next == null) return false;
        return twoPtr(head, head.next.next);
    }

    private boolean twoPtr(ListNode slowPtr, ListNode fastPtr) {
        if (fastPtr.next == null) return false;
        if (fastPtr.next.next == null) return false;
        if (slowPtr == fastPtr || slowPtr == fastPtr.next) return true;
        return twoPtr(slowPtr.next, fastPtr.next.next);
    }
}