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.

Pages: 1 2

3 Responses to “Nth From The End”

1. Globules said

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 xs
```
```\$ ./nthfromend
nthFromEnd1  0 [1,2,3,4,5,6,7,8,9] -> Nothing
nthFromEnd2  0 [1,2,3,4,5,6,7,8,9] -> Nothing
nthFromEnd3  0 [1,2,3,4,5,6,7,8,9] -> Nothing
nthFromEnd1  3 [1,2,3,4,5,6,7,8,9] -> Just 7
nthFromEnd2  3 [1,2,3,4,5,6,7,8,9] -> Just 7
nthFromEnd3  3 [1,2,3,4,5,6,7,8,9] -> Just 7
nthFromEnd1 13 [1,2,3,4,5,6,7,8,9] -> Nothing
nthFromEnd2 13 [1,2,3,4,5,6,7,8,9] -> Nothing
nthFromEnd3 13 [1,2,3,4,5,6,7,8,9] -> Nothing
```
2. Daniel said

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

```#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);
return EXIT_FAILURE;
}
int n = atoi(argv);
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):
1
```
3. sri vignesh said

I know only one.
b= [10,9,8,7,6,5,4,3,2,1,0]
index = 7
print b[len(b) – (index+1)]