前言
回文结构这种之前在做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:如果有不一样,则不是回文结构。否则遍历到两个指针相遇就好了,因为左指针到了右半部分都是右指针走过的路,比较的值也是与之前相同的。文章来源:https://www.toymoban.com/news/detail-832943.html
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模板网!