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 nth 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 nth 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 nth 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.