[已解决]单链表比较步数判断有环

麻麦皮

int HasLoop(LinkList L)
{
        LinkList cur1 = L;
        int pos1 = 0;
        while(cur1)
        {
                LinkList cur2 = L;
                int pos2 = 0;
                while(cur2)
                {
                        if(cur2 == cur1)
                        {
                                if(pos1 == pos2)
                                {
                                        break;
                                }
                                else
                                {
                                        printf("%d", pos2);
                                        return 1;
                                }
                        }
                        cur2 = cur2->next;
                        pos2++;
                }
                cur1 = cur1->next;
                pos1++;
        }
        return 0;
}

cur2 = cur2->next;如果有环的话，不就是在while(cur2)里面死循环了吗

最佳答案

月排行榜 / 总排行榜

Mr、渐行渐远

2020-5-28 20:05:06

麻麦皮 发表于 2020-5-28 17:11
我看懂了你的代码，你看一下我发的代码

while(cur2)里面cur2 = cur2->next不就是无限循环无法退出了吗

这层循环的退出方式分两种情况，并不是直接while条件判断的
1.如果没有回路，外面每循环一次，里层循环最终pos1和pos2会相等，然后break跳到外层循环，
cur1会遍历走到最后一个节点，整个函数结束
2.如果有回路，外面和里面都不会因为指向NULL而停止；cur1走到原本该向前走的地方却向后走了
，而cur2总是从起点出发，这样它们再次相遇的时候cur1走的步数比cur2多，就会执行return语句
直接退出函数
可以调试一下试试

跳转到最佳答案楼层

赚小钱

不懂你的比较步数是什么意思

struct Node {
    int value;
    struct Node *next;
};


struct LinkedList {
    struct Node *head;
};


int linked_list_is_circular(struct LinkedList* list) {
    if (list == NULL || list->head == NULL || list->head->next == NULL) {
        return 0;
    }
    struct Node* slow = list->head;
    struct Node* fast = list->head->next;
    while (fast != NULL && fast->next != NULL) {
        if (slow == fast) {
            return 1;
        }
        slow = slow->next;
        fast = fast->next->next;
    }
    return 0;
}

麻麦皮

赚小钱 发表于 2020-5-26 19:20
不懂你的比较步数是什么意思

你这是快慢指针，小甲鱼线性表14讲了一个方法就是比较步数

赚小钱

麻麦皮 发表于 2020-5-26 19:38
你这是快慢指针，小甲鱼线性表14讲了一个方法就是比较步数

不知道，没看过。 我去找找看一下吧。

Mr、渐行渐远

内层循环目的是让cur2追上cur1，当cur2追上cur1的时候，如果有环，就直接退出函数了，如果没环，就会跳出里面的循环，接着往后走

bool isCircle(LinkList L)
{
        LinkList p, q;
        p = L->next;
        int step_p=0, step_q;
        while(p)
        {
                step_q = 0;
                q = L->next;
                p = p->next;
                step_p ++;
                while(q!=p)
                {
                        q = q->next;
                        step_q ++;
                }
                if(step_p!=step_q)
                {
                        return true;
                }
        }
        return false;
}

麻麦皮

Mr、渐行渐远 发表于 2020-5-28 08:44
内层循环目的是让cur2追上cur1，当cur2追上cur1的时候，如果有环，就直接退出函数了，如果没环，就会跳出里 ...

我看懂了你的代码，你看一下我发的代码

while(cur2)里面cur2 = cur2->next不就是无限循环无法退出了吗

Mr、渐行渐远

麻麦皮 发表于 2020-5-28 17:11
我看懂了你的代码，你看一下我发的代码

while(cur2)里面cur2 = cur2->next不就是无限循环无法退出了吗

这层循环的退出方式分两种情况，并不是直接while条件判断的
1.如果没有回路，外面每循环一次，里层循环最终pos1和pos2会相等，然后break跳到外层循环，
cur1会遍历走到最后一个节点，整个函数结束
2.如果有回路，外面和里面都不会因为指向NULL而停止；cur1走到原本该向前走的地方却向后走了
，而cur2总是从起点出发，这样它们再次相遇的时候cur1走的步数比cur2多，就会执行return语句
直接退出函数
可以调试一下试试

麻麦皮

Mr、渐行渐远 发表于 2020-5-28 20:05
这层循环的退出方式分两种情况，并不是直接while条件判断的
1.如果没有回路，外面每循环一次，里层循环 ...

懂了，我瞎了没看到break以为一直在里面循环