美文网首页
5_9链表的回文结构

5_9链表的回文结构

作者: X_Y | 来源:发表于2017-09-15 12:19 被阅读3次

    请编写一个函数,检查链表是否为回文。

    给定一个链表ListNode* pHead,请返回一个bool,代表链表是否为回文。

    测试样例:
    输入:{1,2,3,2,1}
    返回:true
    输入:{1,2,3,2,3}
    返回:false

    /*
    struct ListNode {
        int val;
        struct ListNode *next;
        ListNode(int x) : val(x), next(NULL) {}
    };*/
    class Palindrome {
    public:
        bool isPalindrome(ListNode* pHead) {
            // write code here
            // 偶数个节点也可以是回文
            ListNode *p1 = pHead, *p2 = pHead;
            stack<int> stk;
            while(p2->next){
                stk.push(p1->val);
                if(p2->next->next){
                    p2 = p2->next->next;
                    p1 = p1->next;
                }else{
                    p2 = p2->next;
                }
            }
            p1 = p1->next;
            while(p1){
                if(p1->val != stk.top()){
                    return false;
                }
                p1 = p1->next;
                stk.pop();
            }
            return true;
        }
    };
    

    相关文章

      网友评论

          本文标题:5_9链表的回文结构

          本文链接:https://www.haomeiwen.com/subject/ssyssxtx.html