【程序员面试金典】面试题 02.06. 回文链表

pppuil 2020-06-13

题目

编写一个函数,检查输入的链表是否是回文的。

示例 1:

输入: 1->2
输出: false

示例 2:

输入: 1->2->2->1
输出: true

思路

利用栈来逆序判断。

代码

时间复杂度:O(n)
空间复杂度:O(n)

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        stack<int> st;
        ListNode *p = head;
        while (p) {
            st.push(p->val);
            p = p->next;
        }
        p = head;
        while (p) {
            int tmp = st.top();
            if (tmp != p->val) return false;
            p = p->next;
            st.pop();
        }
        return true;
    }
};

相关推荐