Cracking The Coding Interview/Q 2.2

From Software Engineers Wiki
Jump to: navigation, search

Implement an algorithm to find the kth to last element of a singly linked list.

Answer

#include <forward_list>

bool find_kth_last(std::forward_list<int>rlist, int last_k, int &ret)
{       
        std::forward_list<int>::iterator ir, ir_kth;

        for (ir = rlist.begin(), ir_kth = ir; ir != rlist.end(); ++ir) {
                if (last_k < 0)
                        ++ir_kth;
                else
                        --last_k;
        }

        if (last_k < 0) {
                ret = *ir_kth;
                return true;
        } else
                return false;
}       

Test program:

int main(void)
{       
        std::forward_list<int> intlist { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
        int i, ret;

        for (i = 0;; ++i) {
                if (!find_kth_last(intlist, i, ret)) {
                        std::cout << i << ": Not found\n";
                        break;
                }
                std::cout << i << ": " << ret << std::endl;
        }

        return 0;
}       

Test result:

0: 0
1: 1
2: 2
3: 3
4: 4
5: 5
6: 6
7: 7
8: 8
9: 9
10: 10
11: Not found
Personal tools
Namespaces

Variants
Actions
Navigation
Toolbox