Cracking The Coding Interview/Q 2.7

From Software Engineers Wiki
Jump to: navigation, search

Implement a function to check if a linked list is palindrome.

Answer

A palindrome is a word, phrase, number, or other sequence of characters which reads the same backward or forward.

If a linked list a palindrome, when the linked list is traversed from front, and from the end, it should have same value until it meets in the middle.

bool list_is_palindrome(std::list<int> &rlist)
{
        std::list<int>::iterator ir_front, ir_end;

        /* if the list is empty, nothing to do */
        if (rlist.empty())
                return true;

        /* find first and last node */
        ir_front = rlist.begin();
        ir_end = rlist.end();
        --ir_end;

        for (;;) {
                /* met in the middle */
                if (ir_front == ir_end)
                        return true;

                /* to be palindrom, should have same value front and end */
                if (*ir_front != *ir_end)
                        return false;

                /* move to the next */
                if (++ir_front == ir_end)
                        return true;
                --ir_end;
        }

        /* this won't reach here */
        return false;
}

Test program:

class list_palindrome_checker {
private:
        std::list<int> m_list;
public:
        list_palindrome_checker(std::initializer_list<int> il) : m_list { il } {
                std::cout << (list_is_palindrome(m_list) ? "true" : "false") << std::endl;
        }
};

int main(void) 
{
        list_palindrome_checker l1 { };
        list_palindrome_checker l2 { 10 };
        list_palindrome_checker l3 { 10, 10 };
        list_palindrome_checker l4 { 10, 20 };
        list_palindrome_checker l5 { 10, 20, 10 };
        list_palindrome_checker l6 { 10, 20, 20, 10 };
        list_palindrome_checker l7 { 10, 20, 30, 20, 10 };
        list_palindrome_checker l8 { 10, 20, 30, 10 };
        list_palindrome_checker l9 { 10, 20, 30, 30, 10 };

        return 0;
}

Test result:

true
true
true
false
true
true
true
false
false
Personal tools
Namespaces

Variants
Actions
Navigation
Toolbox