本文发表在 rolia.net 枫下论坛We can assume the single link list has been defined as below:

template <class T> // Don't use template -2
class SLL // Single link list
{
public:
T current;
SLL<T> * next;
:
:
:
};

The following is the codes for return the nth element from the end of the list:

template <class T>
T * Lastnth(SLL<class T> * const begin, const int step )
// to find the last 3rd, call
// target = (T *)lastnth( begin, 3);
// Time complexity is O(n) // Other method with bigger complexity -5
{

if ( NULL == begin || step <= 0) return NULL; // Don't check parameter -2
// Empty linked list or wrong parameter
if (listclosed( begin)) return NULL; // Don't check closed link -5
// if it's a Closed link list, return NULL,
SLL<T> *b,*f; // f: Fore b:Back
int n = step;
b = f = begin;
while ( f ){
if ( --n > 0 ) f = f->next;
else break;
}
if ( !f ) // Withour consider length < n; n = 0, -3
return &(b->current);
// step == 0 will return the The last element
// If no more than n elements in the link,
// default we return the first element
// If we want return NULL when less than n elements
// modify the above to :
/**
return (n ? NULL : &(b->current);
// n == 0 : n elements, return the first one
// n > 0 : less than n elements, return NULL
// We use red color in test case for this setting
**/

while ( f ) {
f = f->next;
b = b->next;
}
return (void* )&(b->current);
}

Bool listclosed(SLL<class T> * const begin) // Time complexity is O(n)
// If consider link is closed, but time complexity bigger than O(n); -2
{
if ( NULL == begin) return TRUE;
SLL<T> * s, * f; // s: slow, f: fast
s = f = begin;
while (1) {
f = f-> next;
if ( f == s) return TRUE;
else if (f == NULL) return FALSE;
f = f-> next;
if ( f == s) return TRUE;
else if (f == NULL) return FALSE;
s = s->next;
// f moved in the double speed as s, if the list is
// closed, sooner or later, f will pull up to s
}
}更多精彩文章及讨论，请光临枫下论坛 rolia.net