blocks|key|309122|text|因为这听起来像家庭作业，所以我更愿意帮助你自己，而不是给出一个实际的解决方案。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|309123|我建议您在一些小的样本数据集上运行此代码。使用调试器逐步运行各行(可以在函数开始时设置断点)。这应该会让你对代码是如何工作的有一个概念。|309124|您还可以Console.WriteLine()到感兴趣的输出变量。|offset|length|style|CODE|309125|entityMap^0|0|0|4|J|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|M|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|N|8|@$F|O|G|P|H|I]]|9|@]|A|$]]|$1|J|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|K|$]]

Since this sounds like homework, I prefer to help you help yourself instead of giving an actual solution.

I suggest you run this code on some small sample dataset. Use your debugger to run lines step-by-step (you can set a breakpoint at the start of the function). This should give you an idea of how the code works.

You can also <code>Console.WriteLine()</code> to output variables of interest.

blocks|key|309144|text|您的算法首先创建对链表中相隔N个节点的两个节点的引用。因此，在您的示例中，如果N为7，则会将p1设置为8，将p2设置为4。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|309145|然后，它会将每个节点引用前进到列表中的下一个节点，直到p2到达列表中的最后一个元素。同样，在您的示例中，这将是当p1为5，p2为10时。此时，p1引用列表中倒数第N个元素(通过它们相距N个节点的属性)。|309146|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|F|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|G|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|H|8|@]|9|@]|A|$]]]|E|$]]

Your algorithm works by first creating references to two nodes in your linked list that are N nodes apart. Thus, in your example, if N is 7, then it will set p1 to 8 and p2 to 4.

It will then advance each node reference to the next node in the list until p2 reaches the last element in the list. Again, in your example, this will be when p1 is 5 and p2 is 10. At this point, p1 is referring to the Nth to the last element in the list (by the property that they are N nodes apart).

blocks|key|312206|text|该算法的关键是最初通过n-1节点将两个指针p1和p2分开，因此我们希望p2从列表的开头指向(n-1)th节点，然后移动p2，直到它到达列表的last节点。一旦p2到达列表的末尾，p1将指向列表末尾的第n个节点。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|312207|我已经将解释内联为注释。希望它能有所帮助：|312208|//+Function+to+return+the+nth+node+from+the+end+of+a+linked+list.
//+Takes+the+head+pointer+to+the+list+and+n+as+input
//+Returns+the+nth+node+from+the+end+if+one+exists+else+returns+NULL.
LinkedListNode+nthToLast(LinkedListNode+head,+int+n)+{
++//+If+list+does+not+exist+or+if+there+are+no+elements+in+the+list,return+NULL
++if+(head+==+null+%7C%7C+n+<+1)+{
++++return+null;
++}

++//+make+pointers+p1+and+p2+point+to+the+start+of+the+list.
++LinkedListNode+p1+=+head;
++LinkedListNode+p2+=+head;

++//+The+key+to+this+algorithm+is+to+set+p1+and+p2+apart+by+n-1+nodes+initially
++//+so+we+want+p2+to+point+to+the+(n-1)th+node+from+the+start+of+the+list
++//+then+we+move+p2+till+it+reaches+the+last+node+of+the+list.+
++//+Once+p2+reaches+end+of+the+list+p1+will+be+pointing+to+the+nth+node+
++//+from+the+end+of+the+list.

++//+loop+to+move+p2.
++for+(int+j+=+0;+j+<+n+-+1;+%2B%2Bj)+{+
+++//+while+moving+p2+check+if+it+becomes+NULL,+that+is+if+it+reaches+the+end
+++//+of+the+list.+That+would+mean+the+list+has+less+than+n+nodes,+so+its+not+
+++//+possible+to+find+nth+from+last,+so+return+NULL.
+++if+(p2+==+null)+{
+++++++return+null;+
+++}
+++//+move+p2+forward.
+++p2+=+p2.next;
++}

++//+at+this+point+p2+is+(n-1)+nodes+ahead+of+p1.+Now+keep+moving+both+forward
++//+till+p2+reaches+the+last+node+in+the+list.
++while+(p2.next+!=+null)+{
++++p1+=+p1.next;
++++p2+=+p2.next;
++}

+++//+at+this+point+p2+has+reached+the+last+node+in+the+list+and+p1+will+be
+++//+pointing+to+the+nth+node+from+the+last..so+return+it.
+++return+p1;
+}|code-block|syntax|javascript|312209|或者，我们可以将p1和p2设置为n个节点，而不是(n-1)，然后将p2移动到列表的末尾，而不是移动到最后一个节点：|312210|LinkedListNode+p1+=+head;
LinkedListNode+p2+=+head;
for+(int+j+=+0;+j+<+n+;+%2B%2Bj)+{+//+make+then+n+nodes+apart.
++++if+(p2+==+null)+{
++++++++return+null;
++++}
++++p2+=+p2.next;
}
while+(p2+!=+null)+{+//+move+till+p2+goes+past+the+end+of+the+list.
++++p1+=+p1.next;
++++p2+=+p2.next;
}
return+p1;|312211|entityMap^0|B|3|L|2|O|2|Z|2|19|7|1N|2|1Y|4|27|2|2H|2|0|0|0|8|2|B|2|O|5|X|2|0|0^^$0|@$1|2|3|4|5|6|7|S|8|@$9|T|A|U|B|C]|$9|V|A|W|B|C]|$9|X|A|Y|B|C]|$9|Z|A|10|B|C]|$9|11|A|12|B|C]|$9|13|A|14|B|C]|$9|15|A|16|B|C]|$9|17|A|18|B|C]|$9|19|A|1A|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|1B|8|@]|D|@]|E|$]]|$1|H|3|I|5|J|7|1C|8|@]|D|@]|E|$K|L]]|$1|M|3|N|5|6|7|1D|8|@$9|1E|A|1F|B|C]|$9|1G|A|1H|B|C]|$9|1I|A|1J|B|C]|$9|1K|A|1L|B|C]]|D|@]|E|$]]|$1|O|3|P|5|J|7|1M|8|@]|D|@]|E|$K|L]]|$1|Q|3|-4|5|6|7|1N|8|@]|D|@]|E|$]]]|R|$]]

The key to this algorithm is to set two pointers <code>p1</code> and <code>p2</code> apart by <code>n-1</code> nodes initially so we want <code>p2</code> to point to the <code>(n-1)th</code> node from the start of the list then we move <code>p2</code> till it reaches the <code>last</code> node of the list. Once <code>p2</code> reaches end of the list <code>p1</code> will be pointing to the nth node from the end of the list.

I've put the explanation inline as comments. Hope it helps:

<pre><code>// Function to return the nth node from the end of a linked list.
// Takes the head pointer to the list and n as input
// Returns the nth node from the end if one exists else returns NULL.
LinkedListNode nthToLast(LinkedListNode head, int n) {
 // If list does not exist or if there are no elements in the list,return NULL
 if (head == null || n &lt; 1) {
 return null;
 }

 // make pointers p1 and p2 point to the start of the list.
 LinkedListNode p1 = head;
 LinkedListNode p2 = head;

 // The key to this algorithm is to set p1 and p2 apart by n-1 nodes initially
 // so we want p2 to point to the (n-1)th node from the start of the list
 // then we move p2 till it reaches the last node of the list. 
 // Once p2 reaches end of the list p1 will be pointing to the nth node 
 // from the end of the list.

 // loop to move p2.
 for (int j = 0; j &lt; n - 1; ++j) { 
 // while moving p2 check if it becomes NULL, that is if it reaches the end
 // of the list. That would mean the list has less than n nodes, so its not 
 // possible to find nth from last, so return NULL.
 if (p2 == null) {
 return null; 
 }
 // move p2 forward.
 p2 = p2.next;
 }

 // at this point p2 is (n-1) nodes ahead of p1. Now keep moving both forward
 // till p2 reaches the last node in the list.
 while (p2.next != null) {
 p1 = p1.next;
 p2 = p2.next;
 }

 // at this point p2 has reached the last node in the list and p1 will be
 // pointing to the nth node from the last..so return it.
 return p1;
 }
</code></pre>

Alternatively we can set <code>p1</code> and <code>p2</code> apart by n nodes instead of <code>(n-1)</code> and then move <code>p2</code> till the end of the list instead of moving till the last node:

<pre><code>LinkedListNode p1 = head;
LinkedListNode p2 = head;
for (int j = 0; j &lt; n ; ++j) { // make then n nodes apart.
 if (p2 == null) {
 return null;
 }
 p2 = p2.next;
}
while (p2 != null) { // move till p2 goes past the end of the list.
 p1 = p1.next;
 p2 = p2.next;
}
return p1;
</code></pre>

blocks|key|314291|text|你对这种方法有什么看法？|type|unstyled|depth|inlineStyleRanges|entityRanges|data|314292|linkedlist.|314293|Actual+|unordered-list-item|314294|
|314295|Count+linkedlist.|314296|314297|Actual节点索引的长度=|314298|+length+-给定索引；|ordered-list-item|314299|编写一个函数从head遍历并获取上述索引处的节点。|314300|314301|314302|entityMap^0|0|0|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|W|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|X|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|Y|8|@]|9|@]|A|$]]|$1|G|3|H|5|6|7|Z|8|@]|9|@]|A|$]]|$1|I|3|J|5|F|7|10|8|@]|9|@]|A|$]]|$1|K|3|H|5|6|7|11|8|@]|9|@]|A|$]]|$1|L|3|M|5|F|7|12|8|@]|9|@]|A|$]]|$1|N|3|O|5|P|7|13|8|@]|9|@]|A|$]]|$1|Q|3|R|5|P|7|14|8|@]|9|@]|A|$]]|$1|S|3|-4|5|6|7|15|8|@]|9|@]|A|$]]|$1|T|3|-4|5|6|7|16|8|@]|9|@]|A|$]]|$1|U|3|-4|5|6|7|17|8|@]|9|@]|A|$]]]|V|$]]

What do you think regarding this approach.

<ol>
<li>Count length of the linkedlist.</li>
<li>Actual Node index from head = linkedlist length - given index;</li>
<li>Write a function to travesre from head and get the node at the above index.</li>
</ol>

blocks|key|309212|text|我将递归解决方案放在StackOverflow+here中的另一个线程上。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|309213|entityMap|0|LINK|mutability|MUTABLE|url|https://stackoverflow.com/questions/2345347/finding-the-nth-node-from-the-end-of-a-linked-list^0|O|4|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

I have my recursive solution at another thread in StackOverflow <a href="https://stackoverflow.com/questions/2345347/finding-the-nth-node-from-the-end-of-a-linked-list">here</a>

blocks|key|311376|text|不，你不知道链表的长度...你必须经过一次才能得到likedlist的长度，所以你的方法效率很低；|type|unstyled|depth|inlineStyleRanges|entityRanges|data|311377|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

No you dont know the length of the linkedlist ...
You will have to go through once to get length of the likedlist so your approach is little in efficient;

blocks|key|3265258|text|//this++is+the+recursive+solution


//initial+call
find(HEAD,k);

//+main+function
void+find(struct+link+*temp,int+k)
{++
+if(+temp->next+!=+NULL)
+++find(+temp->next,+k);
+if((c%2B%2B)+==+k)+++++++//+c+is+initially+declared+as+1+and+k+is+the+node+to+find+from+last.
++cout<<temp->num<<'+';
}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|3265259|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code>//this is the recursive solution


//initial call
find(HEAD,k);

// main function
void find(struct link *temp,int k)
{ 
 if( temp-&gt;next != NULL)
 find( temp-&gt;next, k);
 if((c++) == k) // c is initially declared as 1 and k is the node to find from last.
 cout&lt;&lt;temp-&gt;num&lt;&lt;' ';
}
</code></pre>

blocks|key|311435|text|我认为问题代码中有一个缺陷，我想知道它是否取自一本书，这是怎么可能的……它可能会正确执行，但代码在逻辑上是不正确的。在for循环中...应该根据p2->next+!+=+NULL检查if条件|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|311436|+for+(int+j+=+0;+j+<+n+-+1;+%2B%2Bj)+{+//+skip+n-1+steps+ahead
+++++++if+(p2->next+==+null)+{
+++++++return+null;+//+not+found+since+list+size+<+n
+++}|code-block|syntax|javascript|311437|...rest是好的，正如已经给出的解释一样，代码将p2+(n-1)位置前移到p1，然后在while循环中同时移动它们，直到p2->next到达末尾。如果你觉得我的答案不正确，我可以随时告诉你|311438|entityMap^0|20|H|0|0|Q|2|T|5|13|2|1Q|8|0^^$0|@$1|2|3|4|5|6|7|O|8|@$9|P|A|Q|B|C]]|D|@]|E|$]]|$1|F|3|G|5|H|7|R|8|@]|D|@]|E|$I|J]]|$1|K|3|L|5|6|7|S|8|@$9|T|A|U|B|C]|$9|V|A|W|B|C]|$9|X|A|Y|B|C]|$9|Z|A|10|B|C]]|D|@]|E|$]]|$1|M|3|-4|5|6|7|11|8|@]|D|@]|E|$]]]|N|$]]

I think there is one flaw in the question code, and I wonder if its been taken from a book how is this possible... it may execute correctly but code is somewhat logically incorrect. Inside the for loop... the if condition should be checked against <code>p2-&gt;next ! = NULL</code>

<pre><code> for (int j = 0; j &lt; n - 1; ++j) { // skip n-1 steps ahead
 if (p2-&gt;next == null) {
 return null; // not found since list size &lt; n
 }
</code></pre>

...rest is fine and explanation as given already the code shifts <code>p2</code> <code>(n-1)</code> positions advance to <code>p1</code>, then in while loop it move them simultaneously till <code>p2-&gt;next</code> reaches the end .. fell free to tell if you find my answer incorrect

blocks|key|312278|text|你也可以使用散列tables.The来解决上面的问题，散列表中的条目是节点的位置和地址。因此，如果我们想要找到从末尾开始的第n个节点(这意味着从第一个节点开始m-n%2B1，其中m是节点数)，当我们输入哈希表条目时，我们得到的nodes.Steps数是：-|type|unstyled|depth|inlineStyleRanges|entityRanges|data|312279|1.遍历每个节点并在哈希表中创建相应的条目。|312280|2.在哈希表中查找m-n%2B1个节点，我们得到了地址。|312281|时间复杂度为O(n)。|312282|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|J|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|K|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|L|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|M|8|@]|9|@]|A|$]]|$1|H|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|I|$]]

You can also solve the above problem using hash tables.The entries of the hash table are position of node and address of node. So if we want to find the nth node from the end(this means m-n+1 from the first where m is number of nodes).Now when we enter the hash table entries we get the number of nodes.Steps are:-

1.Traverse each node and make corresponding entries in hash table.

2.Look for the m-n+1 node in hash table we get the address.

Time complexity is O(n).

blocks|key|3051707|text|职业杯一书中给出的问题略有不同。它说找到单链表的倒数第n个元素。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3051708|下面是我的代码：|3051709|++++public+void+findntolast(int+index)
++++{
++++++++Node+ptr+=+front;+int+count+=+0;
++++++++while(ptr!=null)
++++++++{
++++++++++++count%2B%2B;
++++++++++++if+(count+==+index)
++++++++++++{
++++++++++++++++front+=+ptr;
++++++++++++++++break;
++++++++++++}
++++++++++++ptr+=+ptr.next;
++++++++}
++++++++Node+temp=front;
++++++++while(temp!=null)
++++++++{
++++++++++++Console.WriteLine(temp.data);
++++++++++++temp=temp.next;
++++++++}
++++}|code-block|syntax|javascript|3051710|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|L|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|M|8|@]|9|@]|A|$G|H]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

The problem given in the career cup book is slightly different. It says find the nth to last element of a singly linked list.

Here is my code:

<pre><code> public void findntolast(int index)
 {
 Node ptr = front; int count = 0;
 while(ptr!=null)
 {
 count++;
 if (count == index)
 {
 front = ptr;
 break;
 }
 ptr = ptr.next;
 }
 Node temp=front;
 while(temp!=null)
 {
 Console.WriteLine(temp.data);
 temp=temp.next;
 }
 }
</code></pre>

blocks|key|3051723|text|这只是这个问题的另一种解决方案。虽然时间复杂度保持不变，但此代码在单个循环中实现了解决方案。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3051724|public+Link+findKthElementFromEnd(MyLinkedList+linkedList,+int+k)
++++{
++++++++Link+current+=+linkedList.getFirst();//current+node
++++++++Link+currentK+=+linkedList.getFirst();//node+at+index+k

++++++++int+counter+=+0;

++++++++while(current.getNext()!=null)
++++++++{
++++++++++++counter%2B%2B;

++++++++++++if(counter>=k)
++++++++++++{
++++++++++++++++currentK+=+currentK.getNext();
++++++++++++}

++++++++++++current+=+current.getNext();
++++++++}

++++++++//reached+end
++++++++return+currentK;
++++}|code-block|syntax|javascript|3051725|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Just another solution to this problem. Though the time complexity remains the same, this code achieves the solution in a single loop.

<pre><code>public Link findKthElementFromEnd(MyLinkedList linkedList, int k)
 {
 Link current = linkedList.getFirst();//current node
 Link currentK = linkedList.getFirst();//node at index k

 int counter = 0;

 while(current.getNext()!=null)
 {
 counter++;

 if(counter&gt;=k)
 {
 currentK = currentK.getNext();
 }

 current = current.getNext();
 }

 //reached end
 return currentK;
 }
</code></pre>

blocks|key|309293|text|递归解决方案：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|309294|Node+findKth+(Node+head,+int+count,+int+k)+{
++++if(head+==+null)
++++++++return+head;
++++else+{
++++++++Node+n+=findKth(head.next,count,k);
++++++++count%2B%2B;

++++++++if(count+==+k)
++++++++++++return+head;

++++++++return+n;
++++}
}|code-block|syntax|javascript|309295|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Recursive solution:

<pre><code>Node findKth (Node head, int count, int k) {
 if(head == null)
 return head;
 else {
 Node n =findKth(head.next,count,k);
 count++;

 if(count == k)
 return head;

 return n;
 }
}
</code></pre>

blocks|key|3265443|text|只需在线性时间内反转链表并找到第k个元素。它仍然在线性时间内运行。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3265444|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

Just reverse the linked list in linear time and find the kth element. It still run in linear time.

blocks|key|312354|text|你能使用额外的数据结构吗..如果是这样，那就很简单了.开始将所有节点推送到堆栈中，维护一个计数器并将其弹出。根据您的示例，8->10->5->7->2->1->5->4->10->10+->10开始读取链表，并开始将节点或节点->数据推送到堆栈。所以堆栈看起来像top->{10，10,4，5，1，2，7，5，10，8}<-bottom。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|312355|现在从堆栈的顶部开始弹出，保持一个counter=1，每次弹出时将计数器加1，当达到第n个元素(在您的示例中是第7个元素)时停止弹出。|312356|注意:这将以相反的顺序打印或检索数据/节点|312357|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|I|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|J|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|G|$]]

can you use extra data structure .. if so it will be simple ... start pushing all the nodes to a stack, maintain a counter a pop it. as per your example, 8->10->5->7->2->1->5->4->10->10 start reading the linked list and start pushing the nodes or the node->data onto a stack. so the stack will look like top->{10, 10,4, 5, 1, 2, 7, 5, 10, 8}&lt;-bottom.

now start popping from the top of the stack maintaining a counter=1 and every time you pop increase the counter by 1, when you reach n-th element (in your example 7th element) stop popping.

note: this will print or retrieve the data/nodes in reverse order

blocks|key|314470|text|下面是使用2指针方法的代码：(+source+)|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|314471|慢而快的指针方法|314472|struct+node
{
++int+data;
++struct+node+*next;
}mynode;


mynode+*+nthNodeFrmEnd(mynode+*head,+int+n+/*pass+0+for+last+node*/)
{
++mynode+*ptr1,*ptr2;
++int+count;

++if(!head)
++{
++++return(NULL);
++}

++ptr1++=+head;
++ptr2++=+head;
++count+=+0;

++while(count+<+n)
++{
+++++count%2B%2B;
+++++if((ptr1=ptr1->next)==NULL)
+++++{
++++++++//Length+of+the+linked+list+less+than+n.+Error.
++++++++return(NULL);
+++++}
++}

++while((ptr1=ptr1->next)!=NULL)
++{
++++ptr2=ptr2->next;
++}

++return(ptr2);
}|code-block|syntax|javascript|314473|314474|递归|314475|node*+findNthNode+(node*+head,+int+find,+int&+found){
++++if(!head)+{
++++++++found+=+1;
++++++++return+0;
++++}
++++node*+retval+=+findNthNode(head->next,+find,+found);
++++if(found==find)
++++++++retval+=+head;
++++found+=+found+%2B+1;
++++return+retval;
}|314476|314477|entityMap|0|LINK|mutability|MUTABLE|url|http://k2code.blogspot.in/2010/04/return-nth-node-from-end-of-linked-list.html^0|G|6|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|Y|8|@]|9|@$A|Z|B|10|1|11]]|C|$]]|$1|D|3|E|5|6|7|12|8|@]|9|@]|C|$]]|$1|F|3|G|5|H|7|13|8|@]|9|@]|C|$I|J]]|$1|K|3|-4|5|6|7|14|8|@]|9|@]|C|$]]|$1|L|3|M|5|6|7|15|8|@]|9|@]|C|$]]|$1|N|3|O|5|H|7|16|8|@]|9|@]|C|$I|J]]|$1|P|3|-4|5|6|7|17|8|@]|9|@]|C|$]]|$1|Q|3|-4|5|6|7|18|8|@]|9|@]|C|$]]]|R|$S|$5|T|U|V|C|$W|X]]]]

Here is the code using 2 pointer approach : ( <a href="http://k2code.blogspot.in/2010/04/return-nth-node-from-end-of-linked-list.html" rel="nofollow">source</a> ) 

<h2>Slow and Faster pointer approach</h2>

<pre><code>struct node
{
 int data;
 struct node *next;
}mynode;


mynode * nthNodeFrmEnd(mynode *head, int n /*pass 0 for last node*/)
{
 mynode *ptr1,*ptr2;
 int count;

 if(!head)
 {
 return(NULL);
 }

 ptr1 = head;
 ptr2 = head;
 count = 0;

 while(count &lt; n)
 {
 count++;
 if((ptr1=ptr1-&gt;next)==NULL)
 {
 //Length of the linked list less than n. Error.
 return(NULL);
 }
 }

 while((ptr1=ptr1-&gt;next)!=NULL)
 {
 ptr2=ptr2-&gt;next;
 }

 return(ptr2);
}
</code></pre>

<h2> Recursion</h2>

<pre><code>node* findNthNode (node* head, int find, int&amp; found){
 if(!head) {
 found = 1;
 return 0;
 }
 node* retval = findNthNode(head-&gt;next, find, found);
 if(found==find)
 retval = head;
 found = found + 1;
 return retval;
}
</code></pre>

<hr>

blocks|key|3265634|text|你可以遍历链表并得到大小。一旦你有了大小，你就可以在2n中找到第n项，它仍然是O(n)。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3265635|public+T+nthToLast(int+n)+{
++++//+return+null+if+linkedlist+is+empty
++++if+(head+==+null)+return+null;

++++//+declare+placeholder+where+size+of+linkedlist+will+be+stored
++++//+we+are+hoping+that+size+of+linkedlist+is+less+than+MAX+of+INT
++++int+size+=+0;

++++//+This+is+O(n)+for+sure
++++Node+i+=+head;
++++while+(i.next+!=+null)+{
++++++++size+%2B=+1;
++++++++i+=+i.next;
++++}

++++//+if+user+chose+something+outside+the+size+of+the+linkedlist+return+null
++++if+(size+<+n)
++++++++return+null;

++++//+This+is+O(n)+if+n+==+size
++++i+=+head;
++++while(size+>+n)+{
++++++++size--;
++++++++i+=+i.next;
++++}

++++//+Time+complexity+=+n+%2B+n+=+2n
++++//+therefore+O(n)

++++return+i.value;
}|code-block|syntax|javascript|3265636|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

You can just loop through the linkedlist and get the size. Once you have the size you can find the n'th term in 2n which is O(n) still. 

<pre><code>public T nthToLast(int n) {
 // return null if linkedlist is empty
 if (head == null) return null;

 // declare placeholder where size of linkedlist will be stored
 // we are hoping that size of linkedlist is less than MAX of INT
 int size = 0;

 // This is O(n) for sure
 Node i = head;
 while (i.next != null) {
 size += 1;
 i = i.next;
 }

 // if user chose something outside the size of the linkedlist return null
 if (size &lt; n)
 return null;

 // This is O(n) if n == size
 i = head;
 while(size &gt; n) {
 size--;
 i = i.next;
 }

 // Time complexity = n + n = 2n
 // therefore O(n)

 return i.value;
}
</code></pre>

blocks|key|3052022|text|我们在这里使用两个指针pNode和qNode，它们都是指向头部qNode的初始点。然后，遍历到列表的末尾，只有当计数和位置之间的差异大于0并且pthNode在每个循环中递增一次时，pNode才会遍历。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3052023|static+ListNode+nthNode(int+pos){
ListNode+pNode=head;
ListNode+qNode=head;
int+count+=0;
while(qNode!=null){
++++count%2B%2B;
++++if(count+-+pos+>+0)
++++++++pNode=pNode.next;
++++qNode=qNode.next;
}
return+pNode;
}|code-block|syntax|javascript|3052024|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

We take here two pointers pNode and qNode, both initial points to head qNode. Then, traverse till the end of list and the pNode will only traverse when there's a difference between the count and position is greater than 0 and pthNode increments once in each loop.

<pre><code>static ListNode nthNode(int pos){
ListNode pNode=head;
ListNode qNode=head;
int count =0;
while(qNode!=null){
 count++;
 if(count - pos &gt; 0)
 pNode=pNode.next;
 qNode=qNode.next;
}
return pNode;
}
</code></pre>

blocks|key|3052075|text|我的方法，我认为是简单的，具有O(n)的时间复杂度。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3052076|步骤1:首先获取节点数。运行从第一个节点到最后一个节点的for循环|3052077|步骤2:一旦你有了计数，应用简单的数学，例如，如果我们从最后一个节点找到第7个节点，所有节点的计数是12，那么(+count+-+index)-+1将给出一些第k个节点，你必须遍历到这个节点，它将是从第n个节点到最后一个节点。在这种情况下(12+-7)-1+=4|3052078|如果元素是8->10->5->7->2->1->5->4->10->10，那么结果是第7个到最后一个节点是7，从一开始只是第4个节点。|3052079|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|J|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|K|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|L|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|M|8|@]|9|@]|A|$]]|$1|H|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|I|$]]

my approach, what i think is simple and has time complexity O(n).

Step 1: First get the count of number of nodes. Run a for loop starting from first node to the last node

Step 2: Once you have the count, apply simple math, for example if we have find 7th node to the last node and the count of all nodes is 12, then (count - index)- 1 will give some kth node, upto which you will have to traverse and it will be the nth node to the last node. In this case (12 -7)-1 = 4

If the elements are 8->10->5->7->2->1->5->4->10->10 then the result is 7th to last node is 7, which is nothing but 4th node from the beginning.

blocks|key|3265715|text|public+int+nthFromLast(int+n){
++++Node+current+=+head;
++++Node+reference+=+head;++++++
++++for(int+i=0;i<n;i%2B%2B){
++++++++reference=reference.getNext();
++++}
++++while(reference+!=+null){
++++++++current+=+current.getNext();
++++++++reference+=+reference.getNext();
++++}
++++return+current.getData();
}|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|3265716|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code>public int nthFromLast(int n){
 Node current = head;
 Node reference = head; 
 for(int i=0;i&lt;n;i++){
 reference=reference.getNext();
 }
 while(reference != null){
 current = current.getNext();
 reference = reference.getNext();
 }
 return current.getData();
}
</code></pre>

blocks|key|309439|text|使用两个指针pTemp和NthNode。最初，这两个节点都指向列表的头节点。只有在pTemp进行了n次移动之后，NthNode才开始移动。从两者开始向前移动，直到pTemp到达列表的末尾。因此，NthNode指向从链表末尾开始的第n个节点。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|309440|public+ListNode+NthNodeFromEnd(int+n){
++++ListNode+pTemp+=+head,+NthNode+=+null;
+++for(int+count=1;+count<n;count%2B%2B){
+++++if(pTemp!=null){
+++++++pTemp+=+pTemp.getNext();
+++++}
+++}
+++while(pTemp!=null){
+++++if(NthNode==null){
+++++++++NthNode+=+head;
+++++}
+++++else{
++++++++NthNode+=+NthNode.getNext();
+++++}
+++++pTemp+=+pTemp.getNext();
+++}
+++if(NthNode!=null){
+++++NthNode+=+NthNode.getNext();
+++++return+NthNode;
+++}
return+null;
}|code-block|syntax|javascript|309441|参考TextBook：“在Java中变得简单的数据结构和算法”|309442|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|L|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|M|8|@]|9|@]|A|$]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

Use two pointer pTemp and NthNode. Initially, both points to head node of the list. NthNode starts moving only after pTemp made n moves. From the both moves forward until pTemp reaches end of the list. As a result NthNode points to nth node from the end of the linked list.

<pre><code>public ListNode NthNodeFromEnd(int n){
 ListNode pTemp = head, NthNode = null;
 for(int count=1; count&lt;n;count++){
 if(pTemp!=null){
 pTemp = pTemp.getNext();
 }
 }
 while(pTemp!=null){
 if(NthNode==null){
 NthNode = head;
 }
 else{
 NthNode = NthNode.getNext();
 }
 pTemp = pTemp.getNext();
 }
 if(NthNode!=null){
 NthNode = NthNode.getNext();
 return NthNode;
 }
return null;
}
</code></pre>

Refer TextBook : "Data Structure and Algorithms Made Easy in Java"

blocks|key|314560|text|在java中，我将使用-|type|unstyled|depth|inlineStyleRanges|entityRanges|data|314561|public+class+LL+{
++Node+head;
++int+linksCount;

+++LL(){
+++++head+=+new+Node();
+++++linksCount+=+0;
+++}

++//TRAVERSE+TO+INDEX
++public+Node+getNodeAt(int+index){
++++Node+temp=+head;
++++if(index+>+linksCount){
++++++++System.out.println("index+out+of+bound+!");
++++++++return+null;
++++}
++++for(int+i=0;i<index+&&+(temp.getNext()+!=+null);i%2B%2B){
++++++++temp+=+temp.getNext();
++++}
++++return+temp.getNext();
++}
}|code-block|syntax|javascript|314562|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

In java i will use- 

<pre><code>public class LL {
 Node head;
 int linksCount;

 LL(){
 head = new Node();
 linksCount = 0;
 }

 //TRAVERSE TO INDEX
 public Node getNodeAt(int index){
 Node temp= head;
 if(index &gt; linksCount){
 System.out.println("index out of bound !");
 return null;
 }
 for(int i=0;i&lt;index &amp;&amp; (temp.getNext() != null);i++){
 temp = temp.getNext();
 }
 return temp.getNext();
 }
}
</code></pre>

blocks|key|3052142|text|为了理解这个问题，我们应该用一个测量例子做一个简单的类比。比方说，你必须找到你手臂的位置，离你的中指正好1米远，你如何测量？你只需要抓起一把1米长的尺子，把尺子的顶端放在中指的尖端，那么尺子的底端就正好离中指的顶端1米远。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3052143|我们在这个例子中所做的将是相同的，我们只需要一个具有n个元素宽度的框架，我们必须做的是将该框架放到列表的末尾，因此框架的开始节点将恰好是列表末尾的第n个元素。|3052144|这是我们的列表，假设列表中有M个元素，框架有N个元素宽；|3052145|HEAD+->+EL(1)+->+EL(2)+->+...+->+EL(M-1)+->+EL(M)

<--+Frame+-->|code-block|syntax|javascript|3052146|然而，我们只需要框架的边界，因此框架的结束边界将恰好(N-1)个元素远离框架的开始边界。所以只需要存储这些边界元素。我们称它们为A和B；|3052147|HEAD+->+EL(1)+->+EL(2)+->+...+->+EL(M-1)+->+EL(M)

A+<-+N-Element+Wide->+B|3052148|我们要做的第一件事是找到B，它是帧的结尾。|3052149|ListNode<T>+b+=+head;
int+count+=+1;

while(count+<+n+&&+b+!=+null)+{
++++b+=+b.next;
++++count%2B%2B;
}|3052150|现在，b是数组的第n个元素，a位于HEAD上。所以我们的框架设置好了，我们要做的是一步一步地递增两个边界节点，直到b到达列表的末尾，其中a将是倒数第n个元素；|offset|length|style|BOLD|3052151|ListNode<T>+a+=+head;

while(b.next+!=+null)+{
++++a+=+a.next;
++++b+=+b.next;
}

return+a;|3052152|为了收集所有内容，并使用HEAD检查、N|3052153|public+ListNode<T>+findNthToLast(int+n)+{
++++if(head+==+null)+{
++++++++return+null;
++++}+else+{
++++++++ListNode<T>+b+=+head;
++++++++int+count+=+1;

++++++++while(count+<+n+&&+b+!=+null)+{
++++++++++++b+=+b.next;
++++++++++++count%2B%2B;
++++++++}

++++++++if(count+==+n+&&+b!=null)+{
++++++++++++ListNode<T>+a+=+head;

++++++++++++while(b.next+!=+null)+{
++++++++++++++++a+=+a.next;
++++++++++++++++b+=+b.next;
++++++++++++}

++++++++++++return+a;
++++++++}+else+{
++++++++++++System.out.print("N("+%2B+n+%2B+")+must+be+equal+or+smaller+then+the+size+of+the+list");
++++++++++++return+null;
++++++++}
++++}
}|3052154|
|3052155|3052156|entityMap^0|0|0|0|0|0|0|0|0|3|1|E|1|H|4|1L|1|1W|1|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|19|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|1A|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|1B|8|@]|9|@]|A|$]]|$1|F|3|G|5|H|7|1C|8|@]|9|@]|A|$I|J]]|$1|K|3|L|5|6|7|1D|8|@]|9|@]|A|$]]|$1|M|3|N|5|H|7|1E|8|@]|9|@]|A|$I|J]]|$1|O|3|P|5|6|7|1F|8|@]|9|@]|A|$]]|$1|Q|3|R|5|H|7|1G|8|@]|9|@]|A|$I|J]]|$1|S|3|T|5|6|7|1H|8|@$U|1I|V|1J|W|X]|$U|1K|V|1L|W|X]|$U|1M|V|1N|W|X]|$U|1O|V|1P|W|X]|$U|1Q|V|1R|W|X]]|9|@]|A|$]]|$1|Y|3|Z|5|H|7|1S|8|@]|9|@]|A|$I|J]]|$1|10|3|11|5|6|7|1T|8|@]|9|@]|A|$]]|$1|12|3|13|5|H|7|1U|8|@]|9|@]|A|$I|J]]|$1|14|3|15|5|6|7|1V|8|@]|9|@]|A|$]]|$1|16|3|-4|5|6|7|1W|8|@]|9|@]|A|$]]|$1|17|3|-4|5|6|7|1X|8|@]|9|@]|A|$]]]|18|$]]

To understand this problem, we should do a simple analogy with a measurement example. Let's say, you have to find the place of your arm where exactly 1 meter away from your middle finger, how would you measure? You would just grab a ruler with a 1-meter length and put the top-end of that ruler to the tip of your middle-finger and the bottom-end of the meter will be exactly 1 meter away from the top of your middle-finger.

What we do in this example will be the same, we just need a frame with n-element wide and what we have to do is put the frame to the end of the list, thus the start node of the frame will be exactly n-th element to the end of the list.

This is our list assuming we have M elements in the list, and our frame with N element wide;

<pre><code>HEAD -&gt; EL(1) -&gt; EL(2) -&gt; ... -&gt; EL(M-1) -&gt; EL(M)

&lt;-- Frame --&gt;
</code></pre>

However, we only need the boundaries of the frame, thus the end boundary of the frame will exactly (N-1) elements away from the start boundary of the frame. So have to only store these boundary elements. Let's call them A and B;

<pre><code>HEAD -&gt; EL(1) -&gt; EL(2) -&gt; ... -&gt; EL(M-1) -&gt; EL(M)

A &lt;- N-Element Wide-&gt; B
</code></pre>

The first thing we have to do is finding B, which is the end of the frame. 

<pre><code>ListNode&lt;T&gt; b = head;
int count = 1;

while(count &lt; n &amp;&amp; b != null) {
 b = b.next;
 count++;
}
</code></pre>

Now b is the n-th element of the array, and a is located on the HEAD. So our frame is set, what we will do is increment both boundary nodes step by step until b reachs to the end of the list where a will be n-th-to-the-last element;

<pre><code>ListNode&lt;T&gt; a = head;

while(b.next != null) {
 a = a.next;
 b = b.next;
}

return a;
</code></pre>

To gather up everything, and with the HEAD checks, N &lt; M (where M is the size of the list) checks and other stuff, here is the complete solution method;

<pre><code>public ListNode&lt;T&gt; findNthToLast(int n) {
 if(head == null) {
 return null;
 } else {
 ListNode&lt;T&gt; b = head;
 int count = 1;

 while(count &lt; n &amp;&amp; b != null) {
 b = b.next;
 count++;
 }

 if(count == n &amp;&amp; b!=null) {
 ListNode&lt;T&gt; a = head;

 while(b.next != null) {
 a = a.next;
 b = b.next;
 }

 return a;
 } else {
 System.out.print("N(" + n + ") must be equal or smaller then the size of the list");
 return null;
 }
 }
}
</code></pre>

blocks|key|3052165|text|这里已经有了很多答案，但它们都遍历列表两次(顺序或并行)，或者使用大量额外的存储。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3052166|您可以在遍历列表时使用恒定的额外空格执行此操作(加一点)：|3052167|Node+*getNthFromEnd(Node+*list,+int+n)+{

++++if+(list+==+null+%7C%7C+n<1)+{
++++++++return+null;+//no+such+element
++++}

++++Node+*mark1+=+list,+*mark2+=+list,+*markend+=+list;
++++int+pos1+=+0,+pos2+=+0,+posend+=+0;

++++while+(markend!=null)+{
++++++++if+((posend-pos2)>=(n-1))+{
++++++++++++mark1=mark2;
++++++++++++pos1=pos2;
++++++++++++mark2=markend;
++++++++++++pos2=posend;
++++++++}
++++++++markend=markend->next;
++++++++%2B%2Bposend;
++++}
++++if+(posend<n)+{
++++++++return+null;+//not+enough+elements+in+the+list
++++}

++++//mark1+and+mark2+are+n-1+elements+apart,+and+the+end+is+at+least
++++//1+element+after+mark2,+so+mark1+is+at+least+n+elements+from+the+end

++++while((posend+-+pos1)+>+n)+{
++++++mark1+=+mark1->next;
++++++%2B%2Bpos1;
++++}
++++return+mark1;
}|code-block|syntax|javascript|3052168|这个版本使用了比N%2Bn遍历更少的2个额外指针，其中N是列表的长度，n是参数。|offset|length|style|CODE|3052169|如果你使用M额外的指针，你可以把它写到N%2Bceil(n/(M-1))中(并且你应该把它们存储在一个循环缓冲区中)|3052170|entityMap^0|0|0|0|8|3|P|1|X|1|0|5|1|J|F|0^^$0|@$1|2|3|4|5|6|7|S|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|T|8|@]|9|@]|A|$]]|$1|D|3|E|5|F|7|U|8|@]|9|@]|A|$G|H]]|$1|I|3|J|5|6|7|V|8|@$K|W|L|X|M|N]|$K|Y|L|Z|M|N]|$K|10|L|11|M|N]]|9|@]|A|$]]|$1|O|3|P|5|6|7|12|8|@$K|13|L|14|M|N]|$K|15|L|16|M|N]]|9|@]|A|$]]|$1|Q|3|-4|5|6|7|17|8|@]|9|@]|A|$]]]|R|$]]

There are lots of answers here already, but they all walk the list twice (either sequentially or in parallel) or use a lot of extra storage.

You can do this while walking the list just once (plus a little bit) using constant extra space:

<pre><code>Node *getNthFromEnd(Node *list, int n) {

 if (list == null || n&lt;1) {
 return null; //no such element
 }

 Node *mark1 = list, *mark2 = list, *markend = list;
 int pos1 = 0, pos2 = 0, posend = 0;

 while (markend!=null) {
 if ((posend-pos2)&gt;=(n-1)) {
 mark1=mark2;
 pos1=pos2;
 mark2=markend;
 pos2=posend;
 }
 markend=markend-&gt;next;
 ++posend;
 }
 if (posend&lt;n) {
 return null; //not enough elements in the list
 }

 //mark1 and mark2 are n-1 elements apart, and the end is at least
 //1 element after mark2, so mark1 is at least n elements from the end

 while((posend - pos1) &gt; n) {
 mark1 = mark1-&gt;next;
 ++pos1;
 }
 return mark1;
}
</code></pre>

This version uses 2 extra pointers does less than <code>N+n</code> traversals, where <code>N</code> is the length of the list and <code>n</code> is the argument.

If you use <code>M</code> extra pointers, you can get that down to <code>N+ceil(n/(M-1))</code> (and you should store them in a circular buffer)

blocks|key|3265879|text|这里没有人注意到，如果n大于LinkedList的长度，Jonathan的版本将抛出NullPinterException。以下是我的版本：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3265880|public+Node+nth(int+n){
++++++++if(head+==+null+%7C%7C+n+<+1)+return+null;

++++++++Node+n1+=+head;
++++++++Node+n2+=+head;
++++++++for(int+i+=+1;+i+<+n;+i%2B%2B){
++++++++++++if(n1.next+==+null)+return+null;+
++++++++++++n1+=+n1.next;
++++++++}

++++++++while+(n1.next+!=+null){
++++++++++++n1+=+n1.next;
++++++++++++n2+=+n2.next;
++++++++}
++++++++return+n2;
}|code-block|syntax|javascript|3265881|我在这里只做了一点更改:当节点n1前进时，我不检查n1是否为空，而是检查n1.next是否为空，否则在while循环n1.next中抛出NullPinterException。|3265882|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|L|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|M|8|@]|9|@]|A|$]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

Nobody here noticed that Jonathan's version will throw a NullPinterException if the n is larger that the length of LinkedList.
Here is my version:

<pre><code>public Node nth(int n){
 if(head == null || n &lt; 1) return null;

 Node n1 = head;
 Node n2 = head;
 for(int i = 1; i &lt; n; i++){
 if(n1.next == null) return null; 
 n1 = n1.next;
 }

 while (n1.next != null){
 n1 = n1.next;
 n2 = n2.next;
 }
 return n2;
}
</code></pre>

I just make little change here: when node n1 step forward, instead of checking if n1 is null, I check weather n1.next is null, or else in while loop n1.next will throw a NullPinterException.

blocks|key|311738|text|这是从链表中查找第n个子元素的C#版本。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|311739|public+Node+GetNthLast(Node+head,+int+n)
++++{
++++++++Node+current,+nth;
++++++++current+=+nth+=+head;
++++++++int+counter+=+0;

++++++++while+(current.next+!=+null)
++++++++{
++++++++++++counter%2B%2B;
++++++++++++if+(counter+%25+n+==+0)
++++++++++++{
++++++++++++++++for+(var+i+=+0;+i+<+n+-+1;+i%2B%2B)
++++++++++++++++{
++++++++++++++++++++nth+=+nth.next;
++++++++++++++++}
++++++++++++}
++++++++++++current+=+current.next;
++++++++}
++++++++var+remainingCounts+=+counter+%25+n;
++++++++for+(var+i+=+0;+i+<+remainingCounts;+i%2B%2B)
++++++++{
++++++++++++nth+=+nth.next;
++++++++}
++++++++return+nth;
++++}|code-block|syntax|javascript|311740|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Here is C# version of finding nth child from Linklist.

<pre><code>public Node GetNthLast(Node head, int n)
 {
 Node current, nth;
 current = nth = head;
 int counter = 0;

 while (current.next != null)
 {
 counter++;
 if (counter % n == 0)
 {
 for (var i = 0; i &lt; n - 1; i++)
 {
 nth = nth.next;
 }
 }
 current = current.next;
 }
 var remainingCounts = counter % n;
 for (var i = 0; i &lt; remainingCounts; i++)
 {
 nth = nth.next;
 }
 return nth;
 }
</code></pre>

blocks|key|311752|text|根据内存成本容差(在此解决方案中为O(+k+))，我们可以分配一个长度为k的指针数组，并在遍历链表时用节点作为循环数组填充它。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|311753|当我们遍历完链表，数组的第一个元素(只需确保正确地计算0索引，因为它是一个循环数组)，我们就有了答案。|311754|如果数组的第一个元素为空，那么我们的问题就没有解决方案了。|311755|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|H|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|I|8|@]|9|@]|A|$]]|$1|D|3|E|5|6|7|J|8|@]|9|@]|A|$]]|$1|F|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|G|$]]

Depending of the memory cost tolerance (O(k) in this solution) we could allocate an array of pointers of length k, and populate it with the nodes as a circular array while traversing the linked list. 

When we finish traversing the linked list, the first element of the array (just be sure to calculate the 0-index properly as it's a circular array) we'll have the answer.

If the first element of the array is null, there's no solution to our problem.

blocks|key|3052275|text|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3052276|首先，|3052277|正如评论中提到的，但更清楚的是，这个问题来自：|3052278|3052279|+<Cracking+the+coding+interview+6th>+%7C+IX+Interview+Questions+%7C+2.+Linked+Lists+%7C+Question+2.2。|blockquote|offset|length|style|CODE|3052280|3052281|3052282|这是谷歌的软件工程师Gayle+Laakmann+McDowell写的一本很棒的书，他采访了很多人。|3052283|3052284|方法|3052285|(假设链表不跟踪长度)，在O(n)时间和O(1)空间中有两种方法：|BOLD|3052286|3052287|首先找到长度，然后循环到(len-k%2B1)元素。|unordered-list-item|3052288|3052289|书中没有提到这个解决方案，因为我通过2个指针保持他们(k-1)的距离(+remember.|3052290|Loop，)。|3052291|3052292|这个解决方案来自本书，与问题中的解决方案相同。|3052293|3052294|代码|3052295|下面是带有单元测试的Java实现(不使用JDK语言中的任何高级数据结构)。|3052296|KthToEnd.java|3052297|/**
+*+Find+k-th+element+to+end+of+singly+linked+list,+whose+size+unknown,
+*+1-th+is+the+last,+2-th+is+the+one+before+last,
+*
+*+@author+eric
+*+@date+1/21/19+4:41+PM
+*/
public+class+KthToEnd+{
++++/**
+++++*+Find+the+k-th+to+end+element,+by+find+length+first.
+++++*
+++++*+@param+head
+++++*+@param+k
+++++*+@return
+++++*/
++++public+static+Integer+kthToEndViaLen(LinkedListNode<Integer>+head,+int+k)+{
++++++++int+len+=+head.getCount();+//+find+length,

++++++++if+(len+<+k)+return+null;+//+not+enough+element,

++++++++return+(Integer)+head.getKth(len+-+k).value;+//+get+target+element+with+its+position+calculated,
++++}

++++/**
+++++*+Find+the+k-th+to+end+element,+via+2+pinter+that+has+(k-1)+distance.
+++++*
+++++*+@param+head
+++++*+@param+k
+++++*+@return
+++++*/
++++public+static+Integer+kthToEndVia2Pointer(LinkedListNode<Integer>+head,+int+k)+{
++++++++LinkedListNode<Integer>+p0+=+head;+//+begin+at+0-th+element,
++++++++LinkedListNode<Integer>+p1+=+head.getKth(k+-+1);+//+begin+at+(k-1)-th+element,

++++++++while+(p1.next+!=+null)+{
++++++++++++p0+=+p0.next;
++++++++++++p1+=+p1.next;
++++++++}

++++++++return+p0.value;
++++}

++++static+class+LinkedListNode<T>+{
++++++++private+T+value;
++++++++private+LinkedListNode+next;

++++++++public+LinkedListNode(T+value)+{
++++++++++++this.value+=+value;
++++++++}

++++++++/**
+++++++++*+Append+a+new+node+to+end.
+++++++++*
+++++++++*+@param+value
+++++++++*+@return+new+node
+++++++++*/
++++++++public+LinkedListNode+append(T+value)+{
++++++++++++LinkedListNode+end+=+getEnd();
++++++++++++end.next+=+new+LinkedListNode(value);
++++++++++++return+end.next;
++++++++}

++++++++/**
+++++++++*+Append+a+range+of+number,+range+[start,+end).
+++++++++*
+++++++++*+@param+start+included,
+++++++++*+@param+end+++excluded,
+++++++++*/
++++++++public+void+appendRangeNum(Integer+start,+Integer+end)+{
++++++++++++KthToEnd.LinkedListNode+last+=+getEnd();
++++++++++++for+(int+i+=+start;+i+<+end;+i%2B%2B)+{
++++++++++++++++last+=+last.append(i);
++++++++++++}
++++++++}

++++++++/**
+++++++++*+Get+end+element+of+the+linked+list+this+node+belongs+to,+time+complexity:+O(n).
+++++++++*
+++++++++*+@return
+++++++++*/
++++++++public+LinkedListNode+getEnd()+{
++++++++++++LinkedListNode+end+=+this;
++++++++++++while+(end+!=+null+&&+end.next+!=+null)+{
++++++++++++++++end+=+end.next;
++++++++++++}

++++++++++++return+end;
++++++++}

++++++++/**
+++++++++*+Count+of+element,+with+this+as+head+of+linked+list.
+++++++++*
+++++++++*+@return
+++++++++*/
++++++++public+int+getCount()+{
++++++++++++LinkedListNode+end+=+this;
++++++++++++int+count+=+0;
++++++++++++while+(end+!=+null)+{
++++++++++++++++count%2B%2B;
++++++++++++++++end+=+end.next;
++++++++++++}

++++++++++++return+count;
++++++++}

++++++++/**
+++++++++*+Get+k-th+element+from+beginning,+k+start+from+0.
+++++++++*
+++++++++*+@param+k
+++++++++*+@return
+++++++++*/
++++++++public+LinkedListNode+getKth(int+k)+{
++++++++++++LinkedListNode<T>+target+=+this;
++++++++++++while+(k--+>+0)+{
++++++++++++++++target+=+target.next;
++++++++++++}

++++++++++++return+target;
++++++++}
++++}
}|code-block|syntax|javascript|3052298|KthToEndTest.java|3052299|(单元测试，使用TestNG__，或者根据需要更改为JUnit+/+..+)|3052300|import+org.testng.Assert;
import+org.testng.annotations.BeforeClass;
import+org.testng.annotations.Test;

/**
+*+KthToEnd+test.
+*
+*+@author+eric
+*+@date+1/21/19+5:20+PM
+*/
public+class+KthToEndTest+{
++++private+int+len+=+10;
++++private+KthToEnd.LinkedListNode<Integer>+head;

++++@BeforeClass
++++public+void+prepare()+{
++++++++//+prepare+linked+list+with+value+[0,+len-1],
++++++++head+=+new+KthToEnd.LinkedListNode(0);
++++++++head.appendRangeNum(1,+len);
++++}

++++@Test
++++public+void+testKthToEndViaLen()+{
++++++++//+validate
++++++++for+(int+i+=+1;+i+<=+len;+i%2B%2B)+{
++++++++++++Assert.assertEquals(KthToEnd.kthToEndViaLen(head,+i).intValue(),+len+-+i);
++++++++}
++++}

++++@Test
++++public+void+testKthToEndVia2Pointer()+{
++++++++//+validate
++++++++for+(int+i+=+1;+i+<=+len;+i%2B%2B)+{
++++++++++++Assert.assertEquals(KthToEnd.kthToEndVia2Pointer(head,+i).intValue(),+len+-+i);
++++++++}
++++}
}|3052301|提示：|3052302|3052303|KthToEnd.LinkedListNode|3052304|3052305|它是一个从零开始实现的简单的单链表节点，它代表了一个从自身开始的链表。|3052306|它不会额外跟踪头部/尾部/长度，尽管它有这样做的方法。|3052307|entityMap^0|0|0|0|0|1|Z|13|M|1S|F|2A|C|0|0|0|A|N|0|0|0|D|4|K|4|0|0|0|0|0|0|0|0|0|0|A|4|0|0|D|0|0|0|H|0|8|6|Q|5|0|0|0|3|0|0|0|N|0|0|0|0^^$0|@$1|2|3|-4|4|5|6|22|7|@]|8|@]|9|$]]|$1|A|3|B|4|5|6|23|7|@]|8|@]|9|$]]|$1|C|3|D|4|5|6|24|7|@]|8|@]|9|$]]|$1|E|3|-4|4|5|6|25|7|@]|8|@]|9|$]]|$1|F|3|G|4|H|6|26|7|@$I|27|J|28|K|L]|$I|29|J|2A|K|L]|$I|2B|J|2C|K|L]|$I|2D|J|2E|K|L]]|8|@]|9|$]]|$1|M|3|-4|4|5|6|2F|7|@]|8|@]|9|$]]|$1|N|3|-4|4|5|6|2G|7|@]|8|@]|9|$]]|$1|O|3|P|4|5|6|2H|7|@$I|2I|J|2J|K|L]]|8|@]|9|$]]|$1|Q|3|-4|4|5|6|2K|7|@]|8|@]|9|$]]|$1|R|3|S|4|5|6|2L|7|@]|8|@]|9|$]]|$1|T|3|U|4|5|6|2M|7|@$I|2N|J|2O|K|V]|$I|2P|J|2Q|K|V]]|8|@]|9|$]]|$1|W|3|-4|4|5|6|2R|7|@]|8|@]|9|$]]|$1|X|3|Y|4|Z|6|2S|7|@]|8|@]|9|$]]|$1|10|3|-4|4|5|6|2T|7|@]|8|@]|9|$]]|$1|11|3|12|4|5|6|2U|7|@]|8|@]|9|$]]|$1|13|3|14|4|Z|6|2V|7|@]|8|@]|9|$]]|$1|15|3|-4|4|5|6|2W|7|@]|8|@]|9|$]]|$1|16|3|17|4|5|6|2X|7|@]|8|@]|9|$]]|$1|18|3|-4|4|5|6|2Y|7|@]|8|@]|9|$]]|$1|19|3|1A|4|5|6|2Z|7|@]|8|@]|9|$]]|$1|1B|3|1C|4|5|6|30|7|@$I|31|J|32|K|L]]|8|@]|9|$]]|$1|1D|3|1E|4|5|6|33|7|@$I|34|J|35|K|V]]|8|@]|9|$]]|$1|1F|3|1G|4|1H|6|36|7|@]|8|@]|9|$1I|1J]]|$1|1K|3|1L|4|5|6|37|7|@$I|38|J|39|K|V]]|8|@]|9|$]]|$1|1M|3|1N|4|5|6|3A|7|@$I|3B|J|3C|K|L]|$I|3D|J|3E|K|L]]|8|@]|9|$]]|$1|1O|3|1P|4|1H|6|3F|7|@]|8|@]|9|$1I|1J]]|$1|1Q|3|1R|4|5|6|3G|7|@$I|3H|J|3I|K|V]]|8|@]|9|$]]|$1|1S|3|-4|4|5|6|3J|7|@]|8|@]|9|$]]|$1|1T|3|1U|4|Z|6|3K|7|@$I|3L|J|3M|K|L]]|8|@]|9|$]]|$1|1V|3|-4|4|5|6|3N|7|@]|8|@]|9|$]]|$1|1W|3|1X|4|5|6|3O|7|@]|8|@]|9|$]]|$1|1Y|3|1Z|4|5|6|3P|7|@]|8|@]|9|$]]|$1|20|3|-4|4|5|6|3Q|7|@]|8|@]|9|$]]]|21|$]]

<hr>

<h2>First of all</h2>

As mention in comment, but to be more clear, the question is from: 

<blockquote>
 <code>&lt;Cracking the coding interview 6th&gt;</code> | <code>IX Interview Questions</code> | <code>2. Linked Lists</code> | <code>Question 2.2</code>.
</blockquote>

It's a great book by <code>Gayle Laakmann McDowell</code>, a software engineer from Google, who has interviewed a lot people.

<hr>

<h2>Approaches</h2>

(Assuming the linked list doesn't keep track of length), there are 2 approaches in O(n) time, and O(1) space:

<ul>
<li>Find length first, then loop to the (len-k+1) element. 
This solution is not mentioned in the book, as I remember.</li>
<li>Loop, via 2 pointer, keep them (k-1) distance. 
This solution is from the book, as the same in the question.</li>
</ul>

<hr>

<h2>Code</h2>

Following is the implementation in <code>Java</code>, with unit test, (without using any advanced data structure in JDK itself).

KthToEnd.java

<pre><code>/**
 * Find k-th element to end of singly linked list, whose size unknown,
 * &lt;p&gt;1-th is the last, 2-th is the one before last,
 *
 * @author eric
 * @date 1/21/19 4:41 PM
 */
public class KthToEnd {
 /**
 * Find the k-th to end element, by find length first.
 *
 * @param head
 * @param k
 * @return
 */
 public static Integer kthToEndViaLen(LinkedListNode&lt;Integer&gt; head, int k) {
 int len = head.getCount(); // find length,

 if (len &lt; k) return null; // not enough element,

 return (Integer) head.getKth(len - k).value; // get target element with its position calculated,
 }

 /**
 * Find the k-th to end element, via 2 pinter that has (k-1) distance.
 *
 * @param head
 * @param k
 * @return
 */
 public static Integer kthToEndVia2Pointer(LinkedListNode&lt;Integer&gt; head, int k) {
 LinkedListNode&lt;Integer&gt; p0 = head; // begin at 0-th element,
 LinkedListNode&lt;Integer&gt; p1 = head.getKth(k - 1); // begin at (k-1)-th element,

 while (p1.next != null) {
 p0 = p0.next;
 p1 = p1.next;
 }

 return p0.value;
 }

 static class LinkedListNode&lt;T&gt; {
 private T value;
 private LinkedListNode next;

 public LinkedListNode(T value) {
 this.value = value;
 }

 /**
 * Append a new node to end.
 *
 * @param value
 * @return new node
 */
 public LinkedListNode append(T value) {
 LinkedListNode end = getEnd();
 end.next = new LinkedListNode(value);
 return end.next;
 }

 /**
 * Append a range of number, range [start, end).
 *
 * @param start included,
 * @param end excluded,
 */
 public void appendRangeNum(Integer start, Integer end) {
 KthToEnd.LinkedListNode last = getEnd();
 for (int i = start; i &lt; end; i++) {
 last = last.append(i);
 }
 }

 /**
 * Get end element of the linked list this node belongs to, time complexity: O(n).
 *
 * @return
 */
 public LinkedListNode getEnd() {
 LinkedListNode end = this;
 while (end != null &amp;&amp; end.next != null) {
 end = end.next;
 }

 return end;
 }

 /**
 * Count of element, with this as head of linked list.
 *
 * @return
 */
 public int getCount() {
 LinkedListNode end = this;
 int count = 0;
 while (end != null) {
 count++;
 end = end.next;
 }

 return count;
 }

 /**
 * Get k-th element from beginning, k start from 0.
 *
 * @param k
 * @return
 */
 public LinkedListNode getKth(int k) {
 LinkedListNode&lt;T&gt; target = this;
 while (k-- &gt; 0) {
 target = target.next;
 }

 return target;
 }
 }
}
</code></pre>

KthToEndTest.java

(unit test, using <code>TestNG</code>, or you change to <code>JUnit</code> / .., as wish)

<pre><code>import org.testng.Assert;
import org.testng.annotations.BeforeClass;
import org.testng.annotations.Test;

/**
 * KthToEnd test.
 *
 * @author eric
 * @date 1/21/19 5:20 PM
 */
public class KthToEndTest {
 private int len = 10;
 private KthToEnd.LinkedListNode&lt;Integer&gt; head;

 @BeforeClass
 public void prepare() {
 // prepare linked list with value [0, len-1],
 head = new KthToEnd.LinkedListNode(0);
 head.appendRangeNum(1, len);
 }

 @Test
 public void testKthToEndViaLen() {
 // validate
 for (int i = 1; i &lt;= len; i++) {
 Assert.assertEquals(KthToEnd.kthToEndViaLen(head, i).intValue(), len - i);
 }
 }

 @Test
 public void testKthToEndVia2Pointer() {
 // validate
 for (int i = 1; i &lt;= len; i++) {
 Assert.assertEquals(KthToEnd.kthToEndVia2Pointer(head, i).intValue(), len - i);
 }
 }
}
</code></pre>

Tips:

<ul>
<li><code>KthToEnd.LinkedListNode</code> 
It's a simple singly linked list node implemented from scratch, it represents a linked list start from itself. 
It doesn't additionally track head / tail / length, though it has methods to do that.</li>
</ul>

blocks|key|309604|text|C#中的解决方案。创建一个具有虚拟值的LinkedList。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|309605|++LinkedList<int>+ll+=+new+LinkedList<int>();
++++++++++++ll.AddFirst(10);
++++++++++++ll.AddLast(12);
++++++++++++ll.AddLast(2);
++++++++++++ll.AddLast(8);
++++++++++++ll.AddLast(9);
++++++++++++ll.AddLast(22);
++++++++++++ll.AddLast(17);
++++++++++++ll.AddLast(19);
++++++++++++ll.AddLast(20);|code-block|syntax|javascript|309606|创建两个指向第一个节点的指针p1+&+p1。|309607|++++++++private+static+bool+ReturnKthElement(LinkedList<int>+ll,+int+k)
++++++++{
++++++++++++LinkedListNode<int>+p1+=+ll.First;
++++++++++++LinkedListNode<int>+p2+=+ll.First;|309608|遍历循环，直到p2为null+-这意味着链表长度小于第k个元素，或者直到第k个元素|309609|++++++++++++for+(int+i+=+0;+i+<+k;+i%2B%2B)
++++++++++++{
++++++++++++++++p2+=+p2.Next;
++++++++++++++++if+(p2+==+null)
++++++++++++++++{
++++++++++++++++++++Console.WriteLine($"Linkedlist+is+smaller+than+{k}th+Element");
++++++++++++++++++++return+false;
++++++++++++++++}
++++++++++++}|309610|现在，迭代这两个指针，直到p2为空。包含在p1指针中的值将对应于第k个元素|309611|++++++++++++while+(p2+!=+null)
++++++++++++{
++++++++++++++++p1+=+p1.Next;
++++++++++++++++p2+=+p2.Next;
++++++++++++}
++++++++++++//p1+is+the+Kth+Element
++++++++++++Console.WriteLine($"Kth+element+is+{p1.Value}");
++++++++++++return+true;
++++++++}|309612|entityMap^0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|U|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|V|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|W|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|X|8|@]|9|@]|A|$E|F]]|$1|K|3|L|5|6|7|Y|8|@]|9|@]|A|$]]|$1|M|3|N|5|D|7|Z|8|@]|9|@]|A|$E|F]]|$1|O|3|P|5|6|7|10|8|@]|9|@]|A|$]]|$1|Q|3|R|5|D|7|11|8|@]|9|@]|A|$E|F]]|$1|S|3|-4|5|6|7|12|8|@]|9|@]|A|$]]]|T|$]]

Solution in C#. Create a LinkedList with dummy values.

<pre class="lang-cs prettyprint-override"><code> LinkedList&lt;int&gt; ll = new LinkedList&lt;int&gt;();
 ll.AddFirst(10);
 ll.AddLast(12);
 ll.AddLast(2);
 ll.AddLast(8);
 ll.AddLast(9);
 ll.AddLast(22);
 ll.AddLast(17);
 ll.AddLast(19);
 ll.AddLast(20);
</code></pre>

Create 2 pointers p1 &amp; p1 which point to the First Node.

<pre class="lang-cs prettyprint-override"><code> private static bool ReturnKthElement(LinkedList&lt;int&gt; ll, int k)
 {
 LinkedListNode&lt;int&gt; p1 = ll.First;
 LinkedListNode&lt;int&gt; p2 = ll.First;
</code></pre>

Iterate through the loop till either p2 is null - which means linkedlist length is less than Kth element OR till the Kth element

<pre class="lang-cs prettyprint-override"><code> for (int i = 0; i &lt; k; i++)
 {
 p2 = p2.Next;
 if (p2 == null)
 {
 Console.WriteLine($"Linkedlist is smaller than {k}th Element");
 return false;
 }
 }
</code></pre>

Now, iterate both the pointers till p2 is null. 
Value containted in p1 pointer will correspond to Kth Element

<pre class="lang-cs prettyprint-override"><code>
 while (p2 != null)
 {
 p1 = p1.Next;
 p2 = p2.Next;
 }
 //p1 is the Kth Element
 Console.WriteLine($"Kth element is {p1.Value}");
 return true;
 }
</code></pre>

blocks|key|3052347|text|我只是在操作(插入/删除)过程中维护的"size“变量的帮助下处理这个场景。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|3052348|+++public+int+GetKthFromTheEnd(int+node)
++++{
++++++++var+sizeIndex+=+size;+//++mantained+the+list+size+
++++++++var+currentNode+=+first;
++++++++while+(sizeIndex--+>0)
++++++++{
++++++++++++if+((node+-+1)+==+sizeIndex)
++++++++++++++++return+currentNode.value;

++++++++++++currentNode+=+currentNode.next;
++++++++}

++++++++throw+new+ArgumentNullException();
++++}|code-block|syntax|javascript|3052349|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

I just handle the scenario with the help of the &quot;size&quot; variable which I have maintained during the operation(insert/delete).
<pre><code> public int GetKthFromTheEnd(int node)
 {
 var sizeIndex = size; // mantained the list size 
 var currentNode = first;
 while (sizeIndex-- &gt;0)
 {
 if ((node - 1) == sizeIndex)
 return currentNode.value;

 currentNode = currentNode.next;
 }

 throw new ArgumentNullException();
 }
</code></pre>

The following function is trying to find the <code>nth</code> to last element of a singly linked list.

For example: 

If the elements are <code>8-&gt;10-&gt;5-&gt;7-&gt;2-&gt;1-&gt;5-&gt;4-&gt;10-&gt;10</code> then the result is 
<code>7th</code> to last node is <code>7</code>.

Can anybody help me on how this code is working or is there a better and simpler approach?

<pre><code>LinkedListNode nthToLast(LinkedListNode head, int n) {
 if (head == null || n &lt; 1) {
 return null;
 }

 LinkedListNode p1 = head;
 LinkedListNode p2 = head;

 for (int j = 0; j &lt; n - 1; ++j) { // skip n-1 steps ahead
 if (p2 == null) {
 return null; // not found since list size &lt; n
 }
 p2 = p2.next;
 }

 while (p2.next != null) {
 p1 = p1.next;
 p2 = p2.next;
 }

 return p1;
}
</code></pre>

How to find nth element from the end of a singly linked list?

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

下面的函数尝试查找nth to 单链表的最后一个元素。例如：如果元素为8->10->5->7->2->1->5->4->10->10，则结果为7th to last node is 7。有没有人能帮我讲讲这段代码是如何工作的，或者有没有更好更简单的方法？LinkedListNode nthToLast(LinkedLi...

问如何从单链表的末尾找到第n个元素？
EN

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何从单链表的末尾找到第n个元素？EN