C/C++ BM13 判断一个链表是否为回文结构 |
您所在的位置：网站首页 › 判断是否为回文链表C语言 › C/C++ BM13 判断一个链表是否为回文结构 |
|
文章目录
前言题目解决方案一1.1 思路阐述1.2 源码
解决方案二2.1 思路阐述2.2 源码
总结
前言
回文结构这种之前在做C++入门题的时候，判断回文数的时候遇到过。之前的做法是采用取数，求余等方法来把每一个数取出来再组合进行判断。 在链表中，链表倒置后再相互判断值，比原本取数的方法好像更方便。官方给的理解还是用了双指针法，我这里也会贴。 C/C++ BM1反转链表 题目给定一个链表，请判断该链表是否为回文结构。 回文是指该字符串正序逆序完全一致。 数据范围： 链表节点数 0 ≤ n ≤ 1 0 5 0≤n≤10^5 0≤n≤105，链表中每个节点的值满足 ∣ 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 nums; //将链表元素取出一次放入数组 while(head != NULL){ nums.push_back(head->val); head = head->next; } //双指针指向首尾 int left = 0; int right = nums.size() - 1; //分别从首尾遍历，代表正序和逆序 while(left |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |