Version: Next

141.环形链表

https://leetcode-cn.com/problems/linked-list-cycle/

给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。否则，返回 false 。
进阶：
你能用 O(1)（即，常量）内存解决此问题吗？
示例 1：
输入：head = [3,2,0,-4], pos = 1 输出：true 解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0 输出：true 解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1 输出：false 解释：链表中没有环。
提示：
链表中节点的数目范围是 [0, 104] -105 <= Node.val <= 105 pos 为 -1 或者链表中的一个有效索引。

Given head, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.
Return true if there is a cycle in the linked list. Otherwise, return false.
Follow up:
Can you solve it using O(1) (i.e. constant) memory?
Example 1:
Input: head = [3,2,0,-4], pos = 1 Output: true Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).
Example 2:
Input: head = [1,2], pos = 0 Output: true Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.
Example 3:
Input: head = [1], pos = -1 Output: false Explanation: There is no cycle in the linked list.
Constraints:
The number of the nodes in the list is in the range [0, 104]. -105 <= Node.val <= 105 pos is -1 or a valid index in the linked-list.

快慢指针法

思路

快指针一次走两次，慢指针一次走一次
如果有环，会出现快慢指针相遇，且无法到达null
没有环的话，慢指针永远追不上快指针，即无法相遇，且快指针率先达到空节点null

开始时不能将快慢指针指向同一个节点，因为这样会直接判定为第一个节点上有环
while的退出条件必须加上 fastNode.next != null，否则循环体中的fastNode.next.next可能触发空指针异常

public static boolean hasCycle(ListNode head) {
    if (head == null || head.next == null) return false;

    ListNode slowNode = head;
    ListNode fastNode = head.next;

    while (fastNode != null && fastNode.next != null ) {
        if (slowNode == fastNode) return true;

        slowNode = slowNode.next;
        fastNode = fastNode.next.next;
    }

    return false;
}

测试

public static void main(String[] args) {
    ListNode listNode0 = new ListNode(0);
    ListNode listNode2 = new ListNode(2);
    ListNode listNode3 = new ListNode(3);
    ListNode listNode4 = new ListNode(4);

    listNode3.next = listNode2;
    listNode2.next = listNode0;
    listNode0.next = listNode4;
    listNode4.next = listNode2;

    boolean b = hasCycle(listNode3);
    System.out.println("b = " + b);
}

141.环形链表#

快慢指针法#

思路

测试#

141.环形链表

快慢指针法

测试