牛客：OR36 链表的回文结构

本是古典何须时尚 2024-03-25 15:36 11阅读 0赞

[OR36 链表的回文结构][OR36]  
![在这里插入图片描述][379f76956543422593b83e2a86940712.png]

/*
    struct ListNode {
        int val;
        struct ListNode *next;
        ListNode(int x) : val(x), next(NULL) {}
    };*/
    class PalindromeList {
        
      public:
        bool chkPalindrome(ListNode* A) 
        {
        
            ListNode* shead=(ListNode*)malloc(sizeof(ListNode));
            shead->next=A;
            ListNode* fast=shead;
            ListNode* slow=shead;
            //获得中间节点
            while(fast && fast->next)
            {
        
                fast=fast->next->next;
                slow=slow->next;
            }
    
            ListNode* cur=slow->next;
            ListNode* tmp;
            ListNode* prev=slow;
            slow->next=NULL;
    
            while(1)
            {
        
                tmp=cur->next;
                cur->next=prev;
                if(tmp==NULL) break;
                prev=cur;
                cur=tmp;
            }
    
            ListNode* head=A;
            ListNode* tail=cur;
    
            while(tail!=slow)
            {
        
                if(head->val!=tail->val) return false;
                tail=tail->next;
                head=head->next;
            }
            return true;
        }
    };

详细题解：  
[超级详细，看了绝对有思路][Link 1]

[OR36]: https://www.nowcoder.com/practice/d281619e4b3e4a60a2cc66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking
[379f76956543422593b83e2a86940712.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/2cb682b0f08e4f51b9d23e2f304fea58.png
[Link 1]: https://blog.nowcoder.net/n/7f53f99c5b5f4e51951da71ebb0a7123?f=comment

发表评论取消回复

表情：

评论列表（有 0 条评论，11人围观）

还没有评论，来说两句吧...

相关阅读

相关【数据结构】链表的回文结构

文章目录 * ?引言 * ?\[链表的回文结构\](https://www.nowcoder.com/practice/d281619e4b3e4a60...

ゝ一纸荒年。/ 2024年04月17日 10:43/ 0 赞/ 32 阅读

相关牛客：OR36 链表的回文结构

[OR36 链表的回文结构][OR36] ![在这里插入图片描述][379f76956543422593b83e2a86940712.png] / str

本是古典何须时尚/ 2024年03月25日 15:36/ 0 赞/ 12 阅读

相关牛客网题目--回文数字

题目来源： [点击这里便可以在线编程][Link 1] 题目描述：在不使用额外的内存空间的条件下判断一个整数是否是回文数字提示：负整数可以是回文吗？

女爷i/ 2022年12月06日 15:19/ 0 赞/ 151 阅读

相关回文链表

回文链表 1、参考资料 https://leetcode-cn.com/problems/palindrome-linked-list/ 2、题目 > 题目

柔光的暖阳◎/ 2022年12月03日 09:18/ 0 赞/ 148 阅读

相关回文链表

> 昨天练习了 [验证回文字符串][Link 1] ，回文的定义已经在该篇中定义过了，今天练习 [回文链表][Link 2]。题目描述请判断一个链表是否为回文链表。

逃离我推掉我的手/ 2022年11月11日 05:14/ 0 赞/ 132 阅读

相关链表指定值清除、链表的回文结构

链表指定值清除现在有一个单链表。链表中每个节点保存一个整数，再给定一个值val，把所有等于val的节点删掉。给定一个单链表的头结点head，同时给定一个值val，请

你的名字/ 2022年06月09日 03:19/ 0 赞/ 113 阅读

相关链表的回文结构

题目描述对于一个链表，请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法，判断其是否为回文结构。给定一个链表的头指针A，请返回一个bool值，代表其是否

我会带着你远行/ 2022年06月08日 05:22/ 0 赞/ 99 阅读

相关链表的回文结构

回文链表在我们的生活中经常会碰到这种回文的结构，回文就是反转以后和以前一样的就是回文结构，例如 1->2->3->2->1，我们将它反转之后还是与原链表一样，我们

清疚/ 2022年04月24日 07:04/ 0 赞/ 122 阅读

相关制造回文_牛客网

牛牛有一些字母卡片,每张卡片上都有一个小写字母,所有卡片组成一个字符串s。牛牛一直认为回文这种性质十分优雅,于是牛牛希望用这些卡片拼凑出一些回文串,但是有以下要求: 1、每

灰太狼/ 2021年12月12日 09:13/ 0 赞/ 219 阅读

相关回文链表

请判断一个链表是否为回文链表。示例 1: 输入: 1->2 输出: false 示例 2: 输入: 1->2->

男娘i/ 2021年11月29日 15:16/ 0 赞/ 253 阅读