专门做西装网站,企业网站的优缺点,12黄页网站建设,公司企业网站制作目录
1.问题
2.证明
3.代码实现 1.问题 给你一个链表的头节点 head #xff0c;判断链表中是否有环。 如果链表中有某个节点#xff0c;可以通过连续跟踪 next 指针再次到达#xff0c;则链表中存在环。 为了表示给定链表中的环#xff0c;评测系统内部使用…目录
1.问题
2.证明
3.代码实现 1.问题 给你一个链表的头节点 head 判断链表中是否有环。 如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。注意pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。 如果链表中存在环 则返回 true 。 否则返回 false 。 2.证明 使用快慢指针的方法可以很简单的达到目的慢指针每次走一步快指针每次走两步如果在链表中存在环入环以后快慢指针没走一次他们直接的距离就会减一直至最后它们会在环里面相遇如图 思考一个问题快指针必须走两步吗快指针每次走三步行不行四步呢五步呢N步行不行 假设快指针每次走三步当慢指针入环时它们同时向后走每次它们之间的距离会减少2但是如果它们之间的距离是奇数那么他们这次就不会相遇极限清空下他们每次的距离都是奇数的话那么他们是不是就永远不会相遇了走N步的道理也是一样的。如图 3.代码实现
typedef struct ListNode Node;
bool hasCycle(struct ListNode *head)
{//金典的快慢指针法//快指针每次走两步慢指针每次走一步//快指针先进环慢指针后进环//在环的里面每走一次快慢指针直接的距离缩小1//最终快指针会追上慢指针//如果最终不想交说明链表没有环Node* slow head;Node* fast head;while(fast fast-next){fast fast-next-next;slow slow-next;if(slow fast){//在环里面相遇return true;}}return false;
}
