15 力扣热题刷题记录之第234题回文链表

15 力扣热题刷题记录之第234题回文链表 系列文章目录

力扣热题刷题记录

文章目录

• 系列文章目录
• 前言
• 一、背景
• 二、我的思路
• • 1.用栈记录数值
  • 2.头插法创建新的链表
• 总结

前言

每天进步一点点！！！

一、背景

来源：力扣
链接：https://leetcode-cn.com/problems/palindrome-linked-list/

二、我的思路 1.用栈记录数值

栈是后进先出，正好对比链表从前往后的部分。有点大材小用了，明明数组也可以，但这标签是栈，没想到是用递归栈，绝了！！

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        stack s;
        ListNode*p=head;
        while(p!=NULL)
        {
            s.push(p->val);
            p=p->next;
        }
        for (p=head;p!=nullptr&&p->val==s.top();p=p->next,s.pop())
        {

        }
        if(s.empty())
            return true;
        return false;
    }
};

一开始我是所有比较，后来发现只需比较一半元素即可。

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        stack s;
        ListNode*p=head;
        int i=0;
        while(p!=NULL)
        {
            s.push(p->val);
            p=p->next;
            i++;
        }
        int j=0;
        for (p=head;p!=nullptr&&p->val==s.top()&&j<=i/2;p=p->next,s.pop(),j++)
        {

        }
        if(j==i/2+1)
            return true;
        return false;
    }
};

2.头插法创建新的链表

这个办法其实也浪费空间，后面创建的链表还要和原链表对比，简直麻烦。不如用数组存。（主要一开始我以为链表相等直接可以用==，后来发现要自己一一比对，就算了）

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode*p=head;
        ListNode *myHead=new ListNode(0,nullptr);
        while(p!=NULL)
        {
            ListNode *node=new ListNode(p->val,myHead->next);
            myHead->next=node;
            p=p->next;
        }
        //这里换成链表相等的函数去判断，这里我不写了
        //不改的话，一直是return false的
        if(myHead->next==head)
            return true;
        else return false;
    }
};

总结

其实不难，官方给了一种空间复杂度为1的办法，但是感觉挺麻烦的，就后半部分就地逆置，来跟前半部分比较，但是吧，缺点如下：

来源：力扣
链接：https://leetcode-cn.com/problems/palindrome-linked-list/
喜欢就点个赞叭！