首页 > 试题广场 >

回文链表

[编程题]回文链表
  • 热度指数：29241 时间限制：C/C++ 3秒，其他语言6秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解


现给定一个链表ListNode* pHead，定义bool代表链表是否为回文，请编写程序。

测试样例： 
{1,2,3,2,1}
返回：true
{1,2,3,2,3}
返回：false

说明：本题目包含复杂数据结构ListNode，点此查看相关信息
算法知识视频讲解
添加回答
推荐
九城城主头像 九城城主
思路：利用快慢指针，找到中间节点；将慢指针节点的值压入栈，到达中间节点后，依次出栈与后续节点的值比较。特别注意长度奇偶数。
代码如下：
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class Palindrome {
public:
    bool isPalindrome(ListNode* pHead) {
        // write code here
        if(pHead == NULL)
            return true;
        stack<int> ss;
        ListNode* p = pHead;
        ListNode* q = pHead;
        ss.push(p->val);
        while(q->next != NULL && q->next->next != NULL)
            {
            p = p->next;
           ss.push(p->val);
            q = q->next->next;
        }
        if(q->next == NULL)                                                    //长度为奇数
            ss.pop();
        p = p->next;
        while(!ss.empty())
            {
            if(ss.top() != p->val)
                break;
            p = p->next;
            ss.pop();
        }
        if(ss.empty())
            return true;
        else
            return false;
    }
};
编辑于 2015-08-18 20:51:02 回复(22)
提交观点

问题信息

编程基础 链表
难度：
0条回答 47577浏览

热门推荐

通过挑战的用户

查看代码

相关试题

回文链表

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号