判断链表中是否有环,
这也是力扣的题:
141 Linked List Cycle
142 Linked List Cycle II
146 LRU缓存
不多比比,直接上代码:
变量 mu 指的是 碰头的节点
变量 lamda 指的是 环的长度
static inline Node *move(Node *cur) { return cur ? cur->next : NULL; }
bool cycle_finding(Node *HEAD, Node **TAIL, int *length, int *mu, int *lambda) {
Node *tortoise = move(HEAD);
Node *hare = move(move(HEAD));
while (hare && tortoise) {
tortoise = move(tortoise);
hare = move(move(hare));
}
if (!hare) {
*TAIL = NULL;
*length = 0;
tortoise = HEAD;
while (tortoise && (tortoise = move(tortoise)))
(*length)++;
return false;
}
*mu = 0;
tortoise = HEAD;
while (tortoise != hare) {
(*mu)++;
tortoise = tortoise->next;
hare = hare->next;
}
*lambda = 1;
tortoise = move(tortoise);
*TAIL = tortoise;
while (tortoise != hare) {
*TAIL = tortoise;
(*lambda)++;
tortoise = move(tortoise);
}
*length = *mu + *lambda;
return true;
}
这里面涉及到算法的证明,
自行查阅网上的文章吧:
Floyd判圈算法 (Floyd Cycle Detection Algorithm),又称龟兔赛跑算法 (Tortoise and Hare Algorithm)
代码中获取mu位置,就是算法中证明了的其中一点。
完。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)