2_2.cpp

#include <list>
#include <iostream>

using namespace std;
/*
use the std::list for convenience, avoid using list::end() iterator
need to implement my own list class later
*/

/*
Time: O(N)
Space: O(1)
*/
template<typename T>
typename list<T>::const_iterator reverse_find(const list<T> &li, size_t k){
    typename list<T>::const_iterator i, j;
    i = li.cbegin();
    j = li.cbegin();
    for ( size_t a = 0; a < k; a++){
        i++;
    }
    for (; i != li.cend(); i++){
        j++;
    }
    return j;
}