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;
}
}
read more