How to Check Palindrome Linked List in C/C++?

Given a singly linked list, determine if it is a palindrome.

A palindrome is a string/number that mirrors itself, for example, 21312 reverse is also 21312. We are given a linked list with 1 forward direction, we can convert the list to a vector, which has O(1) random access time compare to O(n) using linked list. However, a better approach is to push the node to a stack as it goes through the list. The second scan would be to compare the element from the stack with the node in the list.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode* p = head;
        stack<int> st;
        while (p != NULL) {
            st.push(p->val); // pushes to the stack
            p = p->next;
        }
        p = head;
        while (!st.empty()) {
            int x = st.top();  // first in last out
            st.pop();
            if (p->val != x) {
                return false;
            }
            p = p->next;
        }
        return true; // stack empty
    }
};

Because the stack implements First In Last Out, if all elements match, the linked list is a palindrome.

–EOF (The Ultimate Computing & Technology Blog) —