Get nth node from end in a linked list

Question

Description:

You’re given the pointer to the head node of a linked list and a specific position. Counting backwards from the tail node of the linked list, get the value of the node at the given position. A position of 0 corresponds to the tail, 1 corresponds to the node before the tail and so on.

Code:

int GetNode(Node head,int n) {
 // This is a "method-only" submission. 
 // You only need to complete this method. 
 Node current = head;
 int count = 0;
 while (current != null) {
 count++;
 current = current.next;
 }
 current = head;
 for (int i = 0; i < count - n - 1; i++) { // extra -1 to avoid going out of linked list.
 current = current.next;
 }
 return current.data;
}

• linac: What if you are passed an empty list (head is null)? How do you want to handle the case of n >= the length of the list? Your code returns the first list element, @janos code will simply fail. In an assignment I would at least want to see that you realized there are potential problems.

Answer 1

Instead of a count variable and reusing current, I think it's neater to use two pointers:

Node runner = head;
for (int i = 0; i < n; i++) {
 runner = runner.next;
}
Node current = head;
while (runner.next != null) {
 runner = runner.next;
 current = current.next;
}
return current.data;

Other than that, your implementation is fine, except for a few tiny style points that are barely worth mentioning, but here we go anyway:

• The commented out instructions about method-only submissions are unnecessary
• Add a space after commas in parameter list

• CodeYogi: I have to agree, a very neat solution indeed. I wonder how to get thinking like that :)
• janos: Me too :-) I saw it once and can't forget about it.
• Frode Akselsen: Implementation in C, Java and Python: geeksforgeeks.org/nth-node-from-the-end-of-a-linked-list