141 环形链表

141 环形链表

/**
 * 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) {
        ListNode p, q;
        if (head == null) {
            return false;
        }    
        else {
            q = head;
            p = head.next;
        }
        // 双指针法，p指针在前，步长为2， q在后，步长为1
        while (p != null && q != null) {
            if (p == q)
                return true;
            // p指针先向前迈进一步，遇到空则一定没有环
            p = p.next;
            if (p == null) {
                return false;
            }
            else {
                p = p.next;
                q = q.next;
            }
        }
        return false;
    }
}