c - 链表有循环函数复习

Question

我写了一个检查链表输入是否有环的代码，但是我的方法和网上的有点不同，行得通吗？

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

}

Answer 1

你回来得太早了:

    for(p2 = p1->next;p2 != NULL;p2=p2->next){
        if(p2 == p1) return 1;
        if (p2 == NULL) return 0;
    }

当p2 变为NULL 时，这只是意味着没有循环涉及p1，而不是根本没有循环。此处返回 0 表示只检查头节点是否有一个周期。

去掉额外的返回值，这样当你搜索完所有内容时你只返回 0。

for(p1 = head;p1->next != NULL;p1 = p1->next){
    for(p2 = p1->next;p2 != NULL;p2=p2->next){
        if(p2 == p1) return 1;
    }
}
return 0;

编辑:

这仍然行不通，因为如果循环不涉及第一个节点，它将进入无限循环。处理这个问题的正确方法是检查每个节点与所有先前找到的节点。这可以通过在访问节点时将节点放入列表中来完成。如果一个节点在你添加之前已经存在于列表中，你就找到了一个循环。

或者，您可以在每个初始化为 0 的节点中放置一个“已访问”标志。然后在遍历列表时设置标志。如果标志已经设置，则您有一个循环。