C++程序检查单链表是否是回文

回文是指正读和反读都一样的字符串，比如 “level”、“racecar”等。在数据结构中，我们也可以用同样的概念来描述一个链表。如果一个单向链表从头到尾和从尾到头都能遍历得到相同的值序列，则称该链表为回文链表。本文将讲述如何编写一个C++程序来检查单链表是否为回文链表。

思路

算法的关键是要找到链表的中间节点，然后反转链表的后半部分，最后比较反转的后半部分和前半部分是否相同。如下图，当链表长度为奇数时，中间节点为 3；当长度为偶数时，中间节点为 4。链表可以用一个结构体表示，包括 val, next两个成员变量表示节点的值和下一个节点的地址。

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

代码实现

根据上述思路，我们可以先统计链表的长度，再从链表头开始向后遍历到中间节点，将前半部分存到一个栈中，然后反转后半部分链表，最后比较反转的后半部分和前半部分是否相同。

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (!head || !head->next) return true; // 边界条件

        // 计算链表的长度
        int len = 0;
        for (ListNode* p = head; p; p = p->next) ++len;

        // 找到中间节点
        int half = (len + 1) / 2;
        ListNode* p = head;
        for (int i = 1; i < half; ++i) p = p->next;

        // 将前半部分存到栈中
        stack<int> st;
        for (ListNode* q = head; q != p; q = q->next) st.push(q->val);

        // 反转后半部分链表
        ListNode* prev = NULL, *cur = p->next;
        while (cur) {
            ListNode* next = cur->next;
            cur->next = prev;
            prev = cur; cur = next;
        }

        // 比较两部分是否相同
        while (p && prev) {
            if (p->val != prev->val) return false;
            p = p->next; prev = prev->next;
        }
        return true;
    }
};

例子

我们用一个例子来说明如何使用isPalindrome()函数。

int main() {
    ListNode* p = new ListNode(1);
    p->next = new ListNode(2);
    p->next->next = new ListNode(3);
    p->next->next->next = new ListNode(2);
    p->next->next->next->next = new ListNode(1);    
    cout << Solution().isPalindrome(p) << endl;  // 输出 1，即链表是回文的

    p->next->next->next->next->next = new ListNode(3);
    cout << Solution().isPalindrome(p) << endl;  // 输出 0，即链表不是回文的

    return 0;
}