LeetCode-循环链表

给定一个链表，判断链表中是否有环。
进阶：
你能否不使用额外空间解决此题？

当初面试的时候，基本上都会问到这个问题

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

解法一： 双指针

利用快慢指针，当两个指针相等时，证明有环。

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;
}