c - Leetcode 第 141 题超出时间限制

Question

这是我的代码，它可以在我的本地编译器上运行。但在 Leetcode 上得到了“Time Limit Exceeded”。

我的想法是让每个节点都指向头节点，然后遍历，如果找到头节点就说明有环。

bool hasCycle(struct ListNode *head) {
    if (head == NULL)
        return false;

    struct ListNode *now;
    struct ListNode *pre;
    now = head;

    pre = now;
    now = now->next;
    pre->next = head;

    while(now != NULL){
        if (now == head){
            return true;
        }

        pre = now;
        now = now->next;
        pre->next = head;
    }

    return false;
}

Answer 1

循环链表有很多种形式，你不能断定head就是链表中的一项。

也许是这样的

head -> a -> b -> c
        ^         |
        |         |
        -----------

你可以定义快指针和慢指针，快的步长为2，慢的步长为1。如果列表是一个循环，那么快最终将等于慢。

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

    struct ListNode* fast;
    struct ListNode* slow;
    fast = head->next->next;
    slow = head->next;

    while (fast && fast->next) {
        if (fast == slow) {
        return true;
        }

        fast = fast->next->next;
        slow = slow->next;
    }

    return false;
}