This is one of frequently asked questions on the programming interview. There are two kinds of solution: iteration-based and recursion-based.

### Data structure

We first define a toy class for the single linked list.

class LinkedListNode { int data; LinkedListNode next; LinkedListNode(int data, LinkedListNode next) { this.data = data; this.next = next; } }

### Iteration-based algorithm

The iteration-based solution is quite tricky but I really like it. In **Cracking the Coding Interview (4ed)**, the solution uses two pointers *p1* and *p2*. Her algorithm first increaments *p2* by *(n-1)* times, and then moves both *p1* and *p2* until *p2.next* reaches the tail of the list. As the result, *p1* points to the *n*th to last element. Because of the copyright, I won’t reproduce her code in this post. If you are interested, please see page 106 for the solution.

### Recursion-based algorithm

The recursion version is straightforward too. We first recursively call a function until we reach the tail of the list. Then we start to count from 0 and increment the counter when a called function is returned. Essentially, it counts the number of **popped** function calls on the call stack. When the counter equals to *n*, we record the element, which is the *n*th to the last.

An easier way to count the number of times we have returned to a recursive call is using a global variable. My solution attempted to avoid it by creating a class **Record** which stores the returned element (null if not) and the counter.

class Record { LinkedListNode node; Integer i; Record(LinkedListNode node, int i) { this.node = node; this.i = i; } }

Then I used a helper function for the recursive purpose.

private static Record nthToLastRurHelper( LinkedListNode head, int n) { if (head == null) { // tail return new Record(null, 0); } Record record = nthToLastRurHelper(head.next, n); record.i++; if (record.i == n) { record.node = head; return record; } else { return record; } }

To find the *n*th to last element, call

static LinkedListNode nthToLastRur(LinkedListNode head, int n) { return nthToLastRurHelper(head, n).node; }

### Test cases

Attached is a snippet code for the testing. The code creates a 10-element linked list, then tests two cases. Both cases should return **true**.

// create a list with 10 elements LinkedListNode head = null; for(int i=10; i>0; i--) { head = new LinkedListNode(i, head); } // return true System.out.println(nthToLastRur(head, 2).data == 9); // return true System.out.println(nthToLastRur(head, 12) == null);

Is there any reason why you wouldn’t want to just iterate through the linked list once to get the size, subtract n from the count to get the nth value and loop over nth through the linked list and return the last node it stops at?

In other words:

public static Node getKthToLast(Node head, int k){

}

public static Node getKthToLast(Node head, int k){

Node iter;

int count = 1;

if(head == null){

return null;

}

else{

while(iter.next != null){

count++;

iter = iter.next;

}

}

int kth = count – k;

iter = head;

for(int i = 0; i < kth; i++){

iter = iter.next;

}

return iter;

}

This is a interview question. I think the challenge of this question IS how to iterate through the list only once.