## Two algorithms to find the nth to last element of a singly linked list

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 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 , we record the element, which is the 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; } }