2. 考研
  3. 单链表有环，是指单链表的最后一个结点的指针指向了链表中的某个结点(通常单链表的最后一个结点的指针域是为空的)。试编写算法判断单链表是否存在环。 (1)给出算法的基本设计思想。 (2)根据设计思想，采用C或C++语言描述算法，关键之处给出注释

单链表有环，是指单链表的最后一个结点的指针指向了链表中的某个结点(通常单链表的最后一个结点的指针域是为空的)。试编写算法判断单链表是否存在环。 (1)给出算法的基本设计思想。 (2)根据设计思想，采用C或C++语言描述算法，关键之处给出注释

admin2018-07-17  20
问题 单链表有环，是指单链表的最后一个结点的指针指向了链表中的某个结点(通常单链表的最后一个结点的指针域是为空的)。试编写算法判断单链表是否存在环。
    (1)给出算法的基本设计思想。
    (2)根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
    (3)说明你所设计算法的时间复杂度和空间复杂度。
选项
答案(1)算法的基本设计思想： 设置两个指针(slow，fast)，初始时都指向头结点，slow每次前进1步，fast每次前进2步。如果链表存在环，则fast必定先进入环，而slow后进入环，两个指针必定相遇。当然，当fast先进入到尾部为NULL，则说明链表中不存在环。 (2)算法的实现如下： bool IsExitsLoop(list *head) { list*slow=head， *fast=head； ／／定义两个指针 while(fast＆＆fast—>next) ／／都不空 { slow=slow—>next； fast=fast—>next—>next， if(slow==fast) ／／相遇，存在环 break； } return !(fast==NULL｜｜fast—>next==NULL)； } 当fast若与slow相遇时，slow肯定没有走遍历完链表，故算法的时间复杂度为O(N)，空间复杂度为O(1)。
解析
转载请注明原文地址:https://kaotiyun.com/show/f8Ri777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)