在一次迭代中查找链表中位置 sqrt(n) 的元素

Question

如何在链表中的位置找到元素sqrt(n(，其中n是一次迭代中链表中元素的数量？在开始之前，我们不知道列表的大小。

Answer 1

您可以使用类似于龟兔算法来检测链表中的周期。具体来说，从列表的开头开始，使用快速指针FP和慢指针SP。然后反复，

• SP前进一步
• FP逐步推进更多步骤：1，然后是3，然后是5，然后是7...

关键是1 + 3 + 5 + 7 + ...(N项(为N²。因此，在N 次重复后，SP将位于位置N，而FP将位于位置N²。每当FP到达链表的末尾时，SP都会持有答案。

Answer 2

最简单的解决方案：

int sqrth(node* head)
{
node* temp1=head;
node* temp2=head;
int k=1;
while(1)
{
int l=k*k;
int r=(k+1)*(k+1)-1;
for(int i=l;temp1->next&&i<r;i++)// e.g. when k=2  range[4,7] return 
temp1=temp1->next;
if(!temp1->next)
return temp2->data;
temp2=temp2->next;
temp1=temp1->next;
k++;
}
}