給定一個鏈表，判斷鏈表中是否有環(huán)。
進(jìn)階：
你能否不使用額外空間解決此題？

當(dāng)初面試的時候，基本上都會問到這個問題

/**
 * Definition for singly-linked list.
 * struct ListNode {
 * int val;
 * struct ListNode *next;
 * };
 */

解法一： 雙指針

利用快慢指針，當(dāng)兩個指針相等時，證明有環(huán)。

bool hasCycle(struct ListNode *head) {
    if(head==NULL || head->next == NULL){
        return false;
    }
    struct ListNode *p, *q;
    p = head;
    q = head;
    while(q!= NULL && q->next != NULL){
        p = p->next;
        q = q->next->next;
        if (p == q ){
            return true;
        }
    }
    return false;
}

解法二： 遞歸

bool hasCycle(struct ListNode *head) {
    if(head==NULL || head->next == NULL){
        return false;
    }
    if(head->next = head) return true;
    ListNode *q = head->next;
    head->next = head;
    bool isCycle = hasCycle(*q);
    return isCycle;
}