骚方法0.0
龟兔赛跑法
快的一次走两步,慢的一次走一步,没环会走出去,有环两个会相遇
时间复杂度O(n),空间复杂度O(1)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *entryNodeOfLoop(ListNode *head) {
ListNode * indexf = head, * indexs = head;
while(indexf != nullptr && indexf->next != nullptr){
indexf = indexf->next->next;
indexs = indexs->next;
if(indexf == indexs) {
ListNode * node = head;
while(node != indexs){
node = node->next;
indexs = indexs->next;
}
return node;
}
}
return nullptr;
}
};