给定一个单向链表，你如何找到第一个从末尾开始的n%k==0，其中n是列表中的元素数，k是一个整数常数？如果 n= 19 且 k =3，那么我们应该返回第 16 个节点。是否可以一次性完成？
我认为这个问题有一些错误，意思是从最后一个 n%k==0 是第 17 个节点而不是第 16 个节点。
检查这个： 1->2->3->4->5->6->7->8->9->10->11->12->13->14->15->16->17->18->19
开始计数：19 在结束的第 1 位。所以 1%3 ！=0
18 位于末尾的第 2 位。所以 2%3 ！=0
17 位于末端的第 3 位。所以 3%3 ==0。
17 是从末端开始的 n%k==0 节点。
是的，我们可以在一次通过中找到它。为此，请参考两个参考，一个是头部，另一个是mod_Node。首先移动你的头部参考，直到k位置，然后开始用头部移动你的mod_Node，一旦你的头部达到空，然后你的mod_Node指向"n%k==0从末端">节点。
public Node modNode(Node head,int k)
{
Node mod_Node=head;
int i=0;
while(head!=null)
{
if(i<k)
i++;
else
mod_Node=mod_Node.next;
head=head.next;
}
return mod_Node;
}
问题只是从链表末尾请求第 k 个元素的不同方式。由于我们n%k=0的末尾的第一个元素必须是第 k 个元素(考虑基于1 的节点索引)。
假设节点总数为 N(我们不知道N)。所以从结束的kth意味着从开始的(N-k+1)th。
现在为了单次通过，我们采用双指针方法。
-
假设我们有两个快指针和慢指针。
-
最初两者都指向列表的头节点。
-
慢速 只有在快移动k-1后才开始移动，即只有在快速从一开始就指向第 k 个元素之后，才开始缓慢移动。
-
从那里开始，两者都向前移动，直到快速到达列表的末尾。
注意：
在任何时间点，两个指针一次移动一个节点。
这意味着一旦快速从开始在第 k个节点处，它就会(N-k)移动到最后一个节点。这意味着慢指针也将从那里移动(N-k)并将到达(N-k + 1)个节点。
一点直觉：要从一开始就到达第 k 个节点，我们需要 (k-1) 移动，所以要从一开始就到达第 (N-k+1)个节点，我们需要 (N-k+1-1)=(N-k
)移动。在快速移动到第 k个节点后，我们只剩下(N-k) 移动。
现在的代码：
//Our structure:
struct Node{
int data;
Node* next;
};
//Function to return the kth node from end.
Node* kthNodeFromEnd(Node* head,int k){
Node *fast,*slow;
int l=1;
fast=slow=head;
while(fast->next!=NULL){
fast=fast->next;
l++;
// Move slow only after fast has reached kth node.
// From there both moves together.
if(l>k){
slow=slow->next;
}
}
return slow;
}
问题澄清：
现在对于 n=19和k=3，如果我们使用基于 1 的索引从一开始就对节点进行编号，我们将得到第 17 个节点作为我们的答案，但是如果我们使用基于 0 的索引对节点进行编号，我们将得到第 16 个节点作为答案。可能是您的问题的来源，对节点进行了基于0 的索引。
注意：">n">定义为列表中的节点数，我们可以以任何方式对节点进行编号。假设对于n=1，我们有第 0 个节点。对于n=2，我们有第 0 个、第 1 个节点，依此类推。
与从末尾查找第 k 个节点相同。
- 取 2 个指针 p 和 q，使它们都指向正面。
- 移动 p 'k-1' 次。
- 只有在然后将 p 和 q 移动 1 步之后，直到 p 成为最后一个节点。 (即直到 p->next 变为 NULL)
- 当 p 到达最后一个节点时，q 将从末尾指向第 k 个节点。
逻辑是我们保持 q 和 p 之间的距离 = 第 k 个节点和最后一个节点之间的距离。
返回索引(假设基于 1 的索引)是k的倍数的最后一个节点。 您可以通过遍历列表并保留索引计数来执行此操作。如果索引恰好是k的倍数，则将其存储在modular_node中。遍历列表时，您的modular_node将从末尾引用n % k节点。对于n = 19且k = 3，最后一个节点将位于索引18处。
def modular_node_from_end(head):
modular_node = None
index_cnt = 1
while head is not None:
if index_cnt % k == 0:
modular_node = head
head = head.link
index_cnt += 1
return mouduar_node.val