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…
import Data.Maybe (listToMaybe) import Data.Vector ((!?)) import qualified Data.Vector as V import Text.Printf (printf) -- Reverse the list, returning the leading element (if any) after having dropped -- the first n-1 elements. nthFromEnd1 :: Int -> [a] -> Maybe a nthFromEnd1 n xs | n > 0 = listToMaybe . drop (n - 1) . reverse $ xs | otherwise = Nothing -- Form a list of key/value pairs, returning the element (if any) whose -- zero-based key is equal to the length of the list minus n. nthFromEnd2 :: Int -> [a] -> Maybe a nthFromEnd2 n xs = let len = length xs in lookup (len - n) $ zip [0..] xs -- Store the list in a vector, returning the element (if any) whose zero-based -- position is the length of the vector minus n. nthFromEnd3 :: Int -> [a] -> Maybe a nthFromEnd3 n xs = let (ys, len) = (V.fromList xs, V.length ys) in ys !? (len - n) test :: Show a => String -> (Int -> [a] -> Maybe a) -> Int -> [a] -> IO () test desc f n xs = let x = f n xs in printf "%s %2d %s -> %s\n" desc n (show xs) (show x) main :: IO () main = do let xs = [1..9] :: [Int] test "nthFromEnd1" nthFromEnd1 0 xs test "nthFromEnd2" nthFromEnd2 0 xs test "nthFromEnd3" nthFromEnd3 0 xs test "nthFromEnd1" nthFromEnd1 3 xs test "nthFromEnd2" nthFromEnd2 3 xs test "nthFromEnd3" nthFromEnd3 3 xs test "nthFromEnd1" nthFromEnd1 13 xs test "nthFromEnd2" nthFromEnd2 13 xs test "nthFromEnd3" nthFromEnd3 13 xsHere’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).
#include <stdio.h> #include <stdlib.h> typedef struct node { int value; struct node* next; } node_t; void print_list(node_t* list) { printf("{"); node_t* node = list; while (node != NULL) { if (node != list) printf("->"); printf("%d", node->value); node = node->next; } printf("}"); } int length(node_t* list) { node_t* node = list; int len = 0; while (node != NULL) { ++len; node = node->next; } return len; } void reverse(node_t** list) { node_t* prev = NULL; node_t* node = NULL; node_t* next = *list; while (next != NULL) { prev = node; node = next; next = next->next; node->next = prev; } *list = node; } // Get length of list. Then walk the list to the // nth element from the end and return. int from_end1(node_t* list, int n) { int len = length(list); node_t* node = list; for (int i = 1; i < len - n; ++i) { node = node->next; } return node->value;; } // Reverse the list. Then get the nth element. // Reverse the list back to its original ordering // and return. int from_end2(node_t** list, int n) { reverse(list); node_t* node = *list; for (int i = 0; i < n; ++i) { node = node->next; } reverse(list); return node->value; } // Walk n elements into the list. Then walk from there // and from the beginning of the list until the first // pointer reaches the end. int from_end3(node_t* list, int n) { node_t* n1 = list; node_t* n2 = list; for (int i = 0; i < n; ++i) { n1 = n1->next; } while (n1 != NULL && n1->next != NULL) { n1 = n1->next; n2 = n2->next; } return n2->value; } int main(int argc, char* argv[]) { if (argc < 2) { fprintf(stderr, "Usage: %s N [X1 [X2 [X3 ...]]]\n", argv[0]); return EXIT_FAILURE; } int n = atoi(argv[1]); node_t* list = NULL; for (int i = argc - 1; i >= 2; --i) { node_t* node = (node_t*)malloc(sizeof(node_t)); node->value = atoi(argv[i]); node->next = list; list = node; } printf("list:\n "); print_list(list); printf("\n"); int e1 = from_end1(list, n); printf("from_end1(list, %d):\n %d\n", n, e1); int e2 = from_end2(&list, n); printf("from_end2(list, %d):\n %d\n", n, e2); int e3 = from_end3(list, n); printf("from_end3(list, %d):\n %d\n", n, e3); node_t* node = list; while (node != NULL) { node_t* next = node->next; free(node); node = next; } return EXIT_SUCCESS; }Example output:
$ ./a.out 0 {0..9} list: {0->1->2->3->4->5->6->7->8->9} from_end1(list, 0): 9 from_end2(list, 0): 9 from_end3(list, 0): 9 $ ./a.out 3 {0..9} list: {0->1->2->3->4->5->6->7->8->9} from_end1(list, 3): 6 from_end2(list, 3): 6 from_end3(list, 3): 6 $ ./a.out 8 {0..9} list: {0->1->2->3->4->5->6->7->8->9} from_end1(list, 8): 1 from_end2(list, 8): 1 from_end3(list, 8): 1I know only one.
b= [10,9,8,7,6,5,4,3,2,1,0]
index = 7
print b[len(b) – (index+1)]