欢迎来到易学考试网 易学考试官网
全部科目 > 大学试题 > 计算机科学 > C++语言程序设计

问答题

简答题

写一算法检测单向链表中是否存在环(whether there is a loop in a link list), 要求算法复杂度(Algorithm’s complexity是O(n)) 并只使用常数空间(space is O(c)). 注意,你只知道一个指向单向链表头的指针。链表的长度是不定的,而且环出现的地方也是不定的,环有可能在头,有可能在中间。而且要求是检测, 不能破坏环的结构.

    【参考答案】

    设两个指针,开始时全部指向链表头,然后开始循环,每次循环中一个指针下移一项,另一个指针下移两项,一直循环至以下两个条件之......

    (↓↓↓ 点击下方‘点击查看答案’看完整答案 ↓↓↓)

    点击查看答案
    微信小程序免费搜题
    微信扫一扫,加关注免费搜题

    微信扫一扫,加关注免费搜题