网站设计基本功能域名免费注册0元注册

这道题要用到快慢指针。

先解释一下什么是快慢指针。

快慢指针有两个指针，走得慢的是慢指针，走得快的是快指针。

在这道题，我们规定慢指针一次走一步，快指针一次走2步。

如果该链表有环，快慢指针最终会在环中相遇；如果没有环，fast指针走到尾节点就结束循环

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
bool hasCycle(struct ListNode *head) {struct ListNode*fast=head,*slow=head;while(fast&&fast->next){slow=slow->next;fast=fast->next->next;if(fast==slow){return true;}}return false;
}

下面我将用数学工具证明一下（其实就是简单的追及问题而已啦）