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

系列文章目录

力扣热题刷题记录

文章目录

前言

每天进步一点点!!!

一、背景

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

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

二、我的思路

1.用栈记录数值

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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        stack<int> 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;
    }
};

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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    bool isPalindrome(ListNode* head) {
        stack<int> 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.头插法创建新的链表

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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
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的办法,但是感觉挺麻烦的,就后半部分就地逆置,来跟前半部分比较,但是吧,缺点如下:

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

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

上一篇:543. 二叉树的直径


下一篇:【RT-Thread&ART-PI】使用软件I2C读取mpu6050