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

Follow up:
Can you solve it without using extra space?

分析

判断一个链表中是否有循环。一种方法是将链表指针依次保存在数组中，看下一个节点是否会在数组中出现，另一种方法是用两个指针，一个前进一步，另一个前进两步，如果存在循环，两个指针肯定有重合的时候。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) {
    struct ListNode *array[100000];
    int num=0;
    struct ListNode *p=head;
    while(p!=NULL)
    {
        for(int i=0;i<num;i++)
        {
            if(p==array[i])
                return true;
        }
        array[num]=p;
        num++;
        p=p->next;
    }
    return false;
}

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) {
    if(head==NULL)
        return false;
    struct ListNode *p1=head,*p2=head->next;
    while(p1!=NULL&&p2!=NULL)
    {
        if(p1==p2)
            return true;
        p1=p1->next;
        if(p2->next!=NULL)
            p2=p2->next->next;
        else
            p2=p2->next;
    }
    return false;
}