【数据结构与算法 经典例题】链表的回文结构(图文详解)

简介: 【数据结构与算法 经典例题】链表的回文结构(图文详解)

一、问题描述

二、解题思路

回文结构(Palindromic structure)是指一个序列或字符串从前往后读和从后往前读是相同的。

计算机科学中,回文结构可以出现在各种数据结构中,如字符串、数组等。对于字符串来说,判断一个字符串是否为回文字符串是一个常见的问题。判断方法是从字符串的两端开始比较字符是否相等,如果都相等,则继续比较下一对字符,直到中间位置。如果在任何时刻存在一对不相等的字符,则该字符串不是回文。

对于数组来说,直接采取上述方法便可以判断是否是回文结构。但对于单链表来说,则是行不通的,因为单链表只能顺序访问,不能随机访问。

判断单链表是否是回文结构的关键是对单链表中元素逐个比较的方法

这里给出的解决思路是:

第一步:

先求出链表的中间结点(对于奇数个节点和偶数个节点的链表可以无差处理)

第二步:

将链表中间结点及以后的节点反转(相当于链表的后半段构成了反转的新的链表)

第三步:

两个指针,分别指向原链表的第一个节点和新链表的第一个节点
将两个指针指向的节点的数据进行比对(这相当于从原链表的两端开始比对)
如果节点的数据不同,返回false
如果节点数据相同,继续比对下一个,直到任一指针指向空,退出循环,返回true

前两步需要单独封装两个函数,分别是求链表的中间节点和反转链表

具体实现可以参考这两篇文章,本文不再详细阐述

【数据结构与算法 刷题系列】求链表的中间结点-CSDN博客

【数据结构与算法刷题系列】(C语言)反转链表-CSDN博客

节点比较和移动的时候,对于奇数个节点的链表和偶数个节点的链表处理方式和效果是相同的,如图

奇数个节点的链表处理过程

1.初始链表

2.求得链表中间节点

3.将中间节点及之后的节点反转

需要注意:

虽然链表后半部分的结构被反转,next指针被改变

但中间节点的前一个节点的next指针未被改变,依然指向初始的中间节点

4.比较过程

两个指针对比指向节点的值,若相等,各走一步

两个指针同时走向了NULL,说明链表为回文结构

偶数个节点的链表处理过程

1.初始链表

2.求得链表中间节点

3.将中间节点及之后的节点反转

4.比较过程

两个指针对比指向节点的值,若相等,各走一步

有一个指针先走向了NULL,说明链表是回文结构

由此也说明,通过比较元素判断回文结构时,有一个指针走向了NULL,就已经完成了判断,应当退出循环

三、C语言代码实现

//链表的回文结构
//对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。
//给定一个链表的头指针A,请返回一个bool值,代表其是否为回文结构。
struct ListNode {
    int val;
    struct ListNode* next;
}; 
struct ListNode* middleNode(struct ListNode* head) { //求链表的中间节点
    struct ListNode* slow, * fast; //创建快慢指针
    slow = fast = head; //初始化
    while (fast && fast->next) { //当快指针可以移动两步时执行循环
        slow = slow->next; //慢指针走一步
        fast = fast->next->next; //快指针走两步
    }
    return slow;//遍历完成时,slow所指节点就是中间节点
}
struct ListNode* reverseList(struct ListNode* head) {
    if (head == NULL)
        return head;//对空链表做特殊处理
    else {
        struct ListNode* n1, * n2, * n3;
        n1 = NULL;
        n2 = head;
        n3 = n2->next;
        while (n2) { //当n2指向空时,链表节点已经遍历完成,next指针修改完成
            n2->next = n1;
            n1 = n2;
            n2 = n3;
            if (n3)//对n3判空,防止对空指针解引用
                n3 = n3->next;
        }
        return n1;//当循环结束时,n1是原链表的尾节点,反转后的首节点
    }
}
bool chkPalindrome(struct ListNode* A) {
    struct ListNode* mid = middleNode(A); //求出中间节点
    struct ListNode* rmid = reverseList(mid);//后半部反转后的中间节点
    while (rmid && A)//节点逐个对比
    {
        if (rmid->val != A->val)
            return false;
        rmid = rmid->next;
        A = A->next;
    }
    return true;;
}

目录
打赏
0
0
0
0
17
分享
相关文章
|
3月前
|
数据结构实验之链表
本实验旨在掌握线性表中元素的前驱、后续概念及链表的建立、插入、删除等算法,并分析时间复杂度,理解链表特点。实验内容包括循环链表应用(约瑟夫回环问题)、删除单链表中重复节点及双向循环链表的设计与实现。通过编程实践,加深对链表数据结构的理解和应用能力。
82 4
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
83 29
|
20天前
|
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
80 25
【C++数据结构——线性表】单链表的基本运算(头歌实践教学平台习题)【合集】
本内容介绍了单链表的基本运算任务,涵盖线性表的基本概念、初始化、销毁、判定是否为空表、求长度、输出、求元素值、按元素值查找、插入和删除数据元素等操作。通过C++代码示例详细解释了顺序表和链表的实现方法,并提供了测试说明、通 - **任务描述**:实现单链表的基本运算。 - **相关知识**:包括线性表的概念、初始化、销毁、判断空表、求长度、输出、求元素值、查找、插入和删除等操作。 - **测试说明**:平台会对你编写的代码进行测试,提供测试输入和预期输出。 - **通关代码**:给出了完整的C++代码实现。 - **测试结果**:展示了测试通过后的预期输出结果。 开始你的任务吧,祝你成功!
43 5
数据结构中二叉树,哈希表,顺序表,链表的比较补充
二叉搜索树,哈希表,顺序表,链表的特点的比较
数据结构中二叉树,哈希表,顺序表,链表的比较补充
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
100 5
【数据结构】树型结构详解 + 堆的实现(c语言)(附源码)
本文介绍了树和二叉树的基本概念及结构,重点讲解了堆这一重要的数据结构。堆是一种特殊的完全二叉树,常用于实现优先队列和高效的排序算法(如堆排序)。文章详细描述了堆的性质、存储方式及其实现方法,包括插入、删除和取堆顶数据等操作的具体实现。通过这些内容,读者可以全面了解堆的原理和应用。
156 16
通过优化算法和代码结构来提升易语言程序的执行效率
通过优化算法和代码结构来提升易语言程序的执行效率
|
3月前
|
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能,支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构,并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示,系统在处理小规模购物车时表现良好,但在大规模购物车操作下可能存在性能瓶颈。
74 0
|
3月前
|
【数据结构】双向带头循环链表(c语言)(附源码)
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点:双向、带头和循环。与单链表相比,它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1),提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现,包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
132 0

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等