Nth From The End
September 11, 2018
One solution is to reverse the list, then count from the front:
(define (nth-last n xs) (list-ref (reverse xs) (- n 1))) > (nth-last 3 '(1 2 3 4 5 6 7 8 9)) 7
Another solution is to pre-calculate the length of the list, then return the appropriate item counting from the front of the list:
(define (nth-last n xs) (list-ref xs (- (length xs) n))) > (nth-last 3 '(1 2 3 4 5 6 7 8 9)) 7
A third solution is to traverse the list keeping two pointers. The first pointer runs through the first n items, then both pointers are incremented simultaneously until the first pointer reaches the end of the list, at which point the second pointer is pointing to the nth-last item:
(define (nth-last n xs) (let loop ((n n) (rabbit xs) (greyhound xs)) (if (positive? n) (loop (- n 1) (cdr rabbit) greyhound) (if (pair? rabbit) (loop n (cdr rabbit) (cdr greyhound)) (car greyhound))))) > (nth-last 3 '(1 2 3 4 5 6 7 8 9)) 7
The greyhound never catches the rabbit.
The first solution allocates space for the reversed list, which you probably don’t want to do. The second solution makes two passes through the list, but the third solution makes only a single pass, so that is probably the one you should prefer.
You can run the program at https://ideone.com/Fm2E9o.
A Haskell version. “Fundamentally different” is in the eye of the beholder…
Here’s a solution in C. n is zero-indexed. It doesn’t handle invalid inputs (e.g., setting n=5 for a list with three elements).
Example output:
I know only one.
b= [10,9,8,7,6,5,4,3,2,1,0]
index = 7
print b[len(b) – (index+1)]