C/C++ BM13 判断一个链表是否为回文结构

这篇具有很好参考价值的文章主要介绍了C/C++ BM13 判断一个链表是否为回文结构。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

前言

回文结构这种之前在做C++入门题的时候,判断回文数的时候遇到过。之前的做法是采用取数,求余等方法来把每一个数取出来再组合进行判断。

在链表中,链表倒置后再相互判断值,比原本取数的方法好像更方便。官方给的理解还是用了双指针法,我这里也会贴。

C/C++ BM1反转链表


题目

给定一个链表,请判断该链表是否为回文结构。
回文是指该字符串正序逆序完全一致。
数据范围: 链表节点数 0 ≤ n ≤ 1 0 5 0≤n≤10^5 0n105,链表中每个节点的值满足 ∣ v a l ∣ ≤ 1 0 7 ∣val∣≤10^7 val∣≤107
示例1
输入:{1}
返回值:true

示例2
输入:{2,1}
返回值:false
说明:2->1

示例3
输入:{1,2,2,1}
返回值:true
说明:1->2->2->1

解决方案一

1.1 思路阐述

这个方法是我立马能想到的,就相当于用两个链表来互相比较,由于要判断是否是有回文的结构,所以要把原始链表倒置后变成另一个链表,再将倒置后的链表与原始链表进行比较即可。

1.2 源码

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 the head
     * @return bool布尔型
     */
    bool isPail(ListNode* head) {
        ListNode* tail=nullptr;
        ListNode* cur=head;
        //倒置链表并创建新链表
        while (head) {
            ListNode* temp=new ListNode(head->val);
            temp->next=tail;
            tail=temp;
            head=head->next;
        }
        head=cur;
        while (head) {
            if(head->val==tail->val)
            {
                head=head->next;
                tail=tail->next;
            }
            else {
                return false;
            }
        }
        return true;
    }
};

解决方案二

2.1 思路阐述

双指针指的是在遍历对象的过程中,不是普通的使用单个指针进行访问,而是使用两个指针(特殊情况甚至可以多个),两个指针或是同方向访问两个链表、或是同方向访问一个链表(快慢指针)、或是相反方向扫描(对撞指针),从而达到我们需要的目的。

具体做法:

step 1:遍历一次链表,将元素取出放入辅助数组中。
step 2:使用下标访问,两个下标代表两个指针,两个指针分别从数组首尾开始遍历,左指针指向开头,从左到右,右指针指向数组末尾,从右到左,依次比较元素是否相同。
step 3:如果有不一样,则不是回文结构。否则遍历到两个指针相遇就好了,因为左指针到了右半部分都是右指针走过的路,比较的值也是与之前相同的。

2.2 源码

class Solution {
public:
    bool isPail(ListNode* head) {
        vector<int> nums;
        //将链表元素取出一次放入数组
        while(head != NULL){ 
            nums.push_back(head->val);
            head = head->next;
        }
        //双指针指向首尾
        int left = 0; 
        int right = nums.size() - 1;
        //分别从首尾遍历,代表正序和逆序
        while(left <= right){ 
            //如果不一致就是不为回文
            if(nums[left] != nums[right]) 
                return false;
            left++;
            right--;
        }
        return true;
    }
};

总结

这题比较简单,方法也有很多,个人觉得在链表题中,链表翻转和双指针法的用途还是比较广的。文章来源地址https://www.toymoban.com/news/detail-832943.html

到了这里,关于C/C++ BM13 判断一个链表是否为回文结构的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 华为OD 面试手撕代码真题【判断链表是否有环】

    判断链表是否有环         面试官口述题目,要求实现函数,输入是一个头节点,输出是一个bool值。         相当经典的题目了,感觉面试官要是出这个题,应该是觉的你还不错,出个简单的做出来就完事儿了。剑指offer或者leetcode上的老题了,但是手撕代码经典的问题还是

    2024年02月10日
    浏览(49)
  • 编写函数,判断一个字符串是否是回文。在主函数中输入一个字符串,调用自定义函数,输出结果。 所谓回文是指顺读和倒读都一样的字符串。如“AMNMA“是回文。

    编写函数,判断一个字符串是否是回文。在主函数中输入一个字符串,调用自定义函数,输出结果。 所谓回文是指顺读和倒读都一样的字符串。如\\\"AMNMA\\\"是回文。 测试输入:abcba 测试输出:是回文! 这道题要求编写一个函数来判断一个字符串是否是回文,并在主函数中调用该

    2024年02月03日
    浏览(64)
  • 链表的回文判断

    思路: 找中间节点–逆置-比较 代码:

    2024年02月07日
    浏览(45)
  • 【面试必刷TOP101】面试官:如何删除有序链表中重复的元素?

    🍳作者: 贤蛋大眼萌,一名很普通但不想普通的程序媛 color{#FF0000}{贤蛋 大眼萌 ,一名很普通但不想普通的程序媛} 贤蛋大眼萌,一名很普通但不想普通的程序媛 🤳 🙊语录: 多一些不为什么的坚持 color{#0000FF}{多一些不为什么的坚持} 多一些不为什么的坚持 📓 专栏:牛

    2024年01月23日
    浏览(46)
  • Java 判断一个数是否是回文数(parlindrome)

    回文数 :从左往右读和从右往左读完全相同的数,如121、12321是回文数,12345不是。 思路 :分别获取到原数字的每一位,反过来组成一个新的数,和原数字比较,若相同则是回文数。 代码 : 关键 : %10获取最后一位,之后将数字/10来去掉这一位,如123%10,得到最后一位3,之

    2024年04月12日
    浏览(53)
  • C++判断一个数是否为回文数的算法

    C++判断一个数是否为回文数的算法 回文数是指正序(从左向右)和倒序(从右向左)读都相同的整数。在C++中,我们可以使用算法来判断一个数是否为回文数。下面是一个详细的解释和相应的源代码。 算法思路: 将给定的整数转换成字符串。 使用双指针法来检查字符串的左

    2024年02月06日
    浏览(53)
  • 判断字符串是否为回文的三种常用编程语言实现

    引言:回文是一种具有镜像对称性的字符串,即它从左到右读和从右到左读是相同的。回文可以在文学、语言学、数学、计算机科学等领域中得到广泛应用。在计算机科学中,判断一个字符串是否为回文是一项基本的算法挑战。在本文中,我们将介绍三种常见的编程语言中用

    2024年02月03日
    浏览(52)
  • Java 算法篇-链表的经典算法:判断回文链表、判断环链表与寻找环入口节点(“龟兔赛跑“算法实现)

    🔥博客主页: 【 小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍       文章目录         1.0 链表的创建         2.0 判断回文链表说明         2.1 快慢指针方法         2.2 使用递归方式实现反转链表方法         2.3 实现判断回文链表 - 使用快慢指针与反转链表

    2024年02月05日
    浏览(61)
  • 面试热题(回文链表)

    给定一个链表的  头节点  head  , 请判断其是否为回文链表。 如果一个链表是回文,那么链表节点序列从前往后看和从后往前看是相同的。        回文链表类似于回文串,正读倒读的顺序是一样的,那么我们怎么去判断一个链表是否是回文链表呢? 今天我们用多种方法、

    2024年02月13日
    浏览(37)
  • 【数据结构】链表的回文结构

    单链表的操作算法是笔试面试中较为常见的题目。 本文将着重介绍平时面试中常见的关于链表的应用题目,马上要进行秋招了。希望对你们有帮助 _ 😀 对于一个链表,请设计一个时间复杂度为O(n),额外空间复杂度为O(1)的算法,判断其是否为回文结构。 给定一个链表的头指针

    2024年02月12日
    浏览(53)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包