牛客：OR36 链表的回文结构

本是古典何须时尚 2024-03-25 15:36 110阅读 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 条评论，110人围观）

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

相关阅读

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

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

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

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

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

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

相关牛客在线编程101-13 判断一个链表是否为回文结构

题目给定一个链表，请判断该链表是否为回文结构。回文是指该字符串正序逆序完全一致。数据范围：链表节点数 0 \\le n \\le 10^50≤n≤10

心已赠人/ 2023年10月04日 19:39/ 0 赞/ 108 阅读

相关【牛客】链表中倒数第K个节点, 链表分割, 链表的回文结构

![在这里插入图片描述][078b66f87e3c4e309d7f34d79c5776c4.gif_pic_center]✨博客主页:[ XIN-XIANG荣][_XIN-XI

╰半橙微兮°/ 2023年09月26日 10:08/ 0 赞/ 85 阅读

相关【牛客网】链表的回文结构

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

傷城~/ 2023年07月04日 03:19/ 0 赞/ 40 阅读

相关【牛客】统计回文

[题目：统计回文][Link 1] 花花非常喜欢拥有对称美的回文串，生日的时候她得到两个礼物分别是字符串A和字符串B。现在她非常好奇有没有办法将字符串B插入字符串A使产生的

水深无声/ 2023年06月13日 13:27/ 0 赞/ 52 阅读

相关牛客回文串

题目描述给定一个字符串，问是否能通过添加一个字母将其变为回文串输入描述 > 一行一个由小写字母构成的字符串，字符串长度小于等于10 输出描述 > 输出答案(Y

Dear 丶/ 2023年05月22日 11:28/ 0 赞/ 86 阅读

相关链表的回文结构

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

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

相关链表的回文结构

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

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

相关制造回文_牛客网

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

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