141. Linked List Cycle

Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.

image

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.

image

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

image

题目要求

判断链表中有没有环，并用pos记录环的位置。

思路

快慢指针法。
慢指针slow和快指针head起始位置均为head，循环遍历链表，慢指针每次走一步，快指针每次走两步。
当slow==fast时，即链表有环。
此时，快指针处在遭遇点不动，让慢指针重新指向head，pos也记录slow的位置，两指针继续向前走，每次都走一步。
则经过数学推导，再次相遇时，即是环的入口点。

代码如下：

public boolean hasCycle(ListNode head) {
        ListNode fast=head;
        ListNode slow=head;
        int pos=-1;
        
        while(fast!=null&&fast.next!=null) {//←一般涉及.next.next的操作，都要这样判断循环条件
            slow=slow.next;
            fast=fast.next.next;
            if (fast==slow) {
                slow=head;
                while(slow!=fast) {
                    slow=slow.next;
                    fast=fast.next;
                    pos++;
                }
                System.out.println(pos);
                return true;
            }
        }

        return false;

    }

class ListNode {//链表类结构
        int val;
        ListNode next;
        ListNode(int x) {
            val = x;
            next = null;
        }
    }