Nth From The End
September 11, 2018
Counting from the end of the list, the third-last item in the list (1 2 3 4 5 6 7 8 9) is 7.
Your task is to write a program to find the nth-last item in a list; you must provide at least three fundamentally different solutions. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Programming Praxis 
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)]