【数据结构OJ题】链表的回文结构

简介: 牛客题目——链表的回文结构

1. 题目描述

7354680268c841f8aa30fa8455c3903c.png

2. 思路分析

在做这道题之前,我们首先得知道什么是“回文”。

回文就是指正读和反读都相同的字符序列为“回文”,如“abba”、“abccba”、12321、123321是“回文”,“abcde”和“ababab”则不是“回文”。

知道了回文的意思后,我们开始分析题目!

先找到中间结点,然后把后半部分逆置,最后对前后两部分一一比对,如果结点的值全部相同,则即为回文。否则就不是回文

如果链表是回文结构如下图(左半部分为奇数个结点的情况,右半部分为偶数个结点的情况)
ba1bf3c606018db2c65c3c0924a855f4.png

如果有小伙伴不知道怎么求链表的中间结点,可以看看这篇文章:

https://blog.csdn.net/m0_62531913/article/details/132309395?spm=1001.2014.3001.5502

如果有小伙伴不知道怎么将链表逆置,可以看看这篇文章:

https://blog.csdn.net/m0_62531913/article/details/132297310?spm=1001.2014.3001.5502

3. 代码实现

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};*/
class PalindromeList {
   
public:
    struct ListNode* middleNode(struct ListNode* head){
   
        struct ListNode *slow=head,*fast=head;
        while(fast&&fast->next)
        {
   
            slow=slow->next;
            fast=fast->next->next;
        }
        return slow;
    }
    struct ListNode* reverseList(struct ListNode* head){
   
        struct ListNode *n1,*n2,*n3;
        n1=NULL;
        n2=head;
        if(n2)
            n3=n2->next;
        while(n2)
        {
   
            n2->next=n1;
            n1=n2;
            n2=n3;
            if(n3)
                n3=n3->next;
        }
        return n1;
    }
    bool chkPalindrome(ListNode* head) {
   
        struct ListNode* mid=middleNode(head);
        struct ListNode* rmid=reverseList(mid);
        while(head&&rmid)
        {
   
            if(head->val!=rmid->val)
            {
   
                return false;
            }
            else
            {
   
                head=head->next;
                rmid=rmid->next;
            }
        }
        return true;
    }
};

b272946431daab093cc2a11e4d9df550.png

相关文章
|
4天前
|
存储 C语言
【数据结构】c语言链表的创建插入、删除、查询、元素翻倍
【数据结构】c语言链表的创建插入、删除、查询、元素翻倍
【数据结构】c语言链表的创建插入、删除、查询、元素翻倍
|
3天前
|
存储 缓存 算法
深入解析B树:数据结构、存储结构与算法优势
深入解析B树:数据结构、存储结构与算法优势
|
3天前
|
算法
【数据结构与算法】共享双向链表
【数据结构与算法】共享双向链表
4 0
|
3天前
|
算法
【数据结构与算法】双向链表
【数据结构与算法】双向链表
4 0
|
3天前
|
算法
【数据结构与算法】循环链表
【数据结构与算法】循环链表
4 0
|
3天前
|
存储 算法
【数据结构与算法】链表
【数据结构与算法】链表
4 0
|
2月前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
2月前
|
存储 SQL 算法
LeetCode 题目 86:分隔链表
LeetCode 题目 86:分隔链表
|
2月前
|
存储 算法 Java
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
17 2
|
3月前
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点.
<数据结构>五道LeetCode链表题分析.环形链表,反转链表,合并链表,找中间节点
36 1