这道题要用到快慢指针。
先解释一下什么是快慢指针。
快慢指针有两个指针,走得慢的是慢指针,走得快的是快指针。
在这道题,我们规定慢指针一次走一步,快指针一次走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;
}
下面我将用数学工具证明一下(其实就是简单的追及问题而已啦)