LeetCode 热题 100_回文链表(24_234_简单_C++)（哈希表)(单链表；将值复制到数组中后用双指针法；快慢指针寻找中间节点+反转链表)
LeetCode 热题 100_回文链表（24_234）
题目描述：
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
输入输出样例：
示例 1：
输入：head = [1,2,2,1]
输出：true
示例 2：
输入：head = [1,2]
输出：false
提示：
链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9
进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
题解：
解题思路：
思路一（将值复制到数组中后用双指针法）：
1、创建一个额外的数组，将链表中的值存入数组中，通过数组进行回文的判断。
2、复杂度分析：
① 时间复杂度：O(n)，其中 n 指的是链表的元素个数。 遍历链表并将值复制到数组中，O(n)。双指针判断是否为回文，执行了 O(n/2) 次的判断，即 O(n)。总的时间复杂度：O(2n)=O(n)。
② 空间复杂度：O(n)，其中 n 指的是链表的元素个数，我们使用了一个数组列表存放链表的元素值。
思路二（快慢指针寻找中间节点+反转链表）：
1、我们可以找到中间结点，然后将后半部分链表反转，再通过比较前半部分和后半部分是否构成回文链表，最后将后半部分链表复原。
2、具体思路如下：
① 查找中间结点（使用快慢指针）。
② 通过查找的中间结点将后半部分链表反转。
③ 逐个比较前半部分和后半部分是否构成回文链表。
④ 将后半部分链表复原。
3、复杂度分析
① 时间复杂度：O(n)，其中 n 是链表的长度（节点个数）。查找中间结点为O(n/2)，将后半部分链表反转为O(n/2)，逐个比较前半部分和后半部分是否构成回文链表为O(n/2)， 将后半部分链表复原为O(n/2)，所以总的时间复杂度为O(n)。
② 空间复杂度：O(1)，对原链表进行操作，使用常熟个额外空间。
代码实现
代码实现（思路一（将值复制到数组中后用双指针法））：
bool isPalindrome1(ListNode* head) {
ListNode *p=head;
vector<int> a;
//将链表中的数据存入容器a
while(p!=nullptr){
a.emplace_back(p->val);
p=p->next;
}
//判断a中的数据是否构成回文
for(int i=0;i<a.size()/2;i++){
if(a[i]!=a[a.size()-1-i]){
return false;
}
}
return true;
}
代码实现（思路二（快慢指针寻找中间节点+反转链表））：
//1->2->3->null 中间结点2
//1->2->3->4->null 中间结点3
//快慢指针查找中间结点
ListNode* findMiddleNode(ListNode *head){
ListNode *slow=head,*fast=head;
while(fast!=nullptr&&fast->next!=nullptr){
fast=fast->next->next;
slow=slow->next;
}
return slow;
}
//将后半部分的结点翻转
ListNode* reverseList(ListNode* head){
ListNode *tmp=head,*pre=nullptr,*r=head;
while(r!=nullptr){
r=r->next;
tmp->next=pre;
pre=tmp;
tmp=r;
}
return pre;
}
//判断前后两端是否构成回文链表
bool isPalindrome2(ListNode* head) {
//查找中间结点
ListNode *middleNode=findMiddleNode(head);
//通过查找的中间结点将后半部分链表反转。
ListNode *head2=reverseList(middleNode);
//用于还原后半部分链表
ListNode *p=head2;
//逐个比较前半部分和后半部分是否构成回文链表。
while(head2!=nullptr){
if(head->val!=head2->val){
//将后半部分链表复原。
reverseList(p);
return false;
}
head=head->next;
head2=head2->next;
}
//将后半部分链表复原
reverseList(p);
return true;
}
以思路二为例完成代码调试
#include<iostream>
#include<vector>
using namespace std;
struct ListNode{
int val;
ListNode *next;
ListNode():val(0),next(nullptr){}
ListNode(int x):val(x),next(nullptr){}
ListNode(int x,ListNode *next):val(x),next(next){}
};
//尾插法创建单链表
ListNode* createList(vector<int> a){
ListNode *head=nullptr,*tail=nullptr;
for(const auto val:a){
ListNode *newNode=new ListNode(val);
if(head==nullptr){
head=newNode;
tail=newNode;
}else{
tail->next=newNode;
tail=newNode;
}
}
return head;
}
//1->2->3->null 中间结点2
//1->2->3->4->null 中间结点3
//查找中间结点
ListNode* findMiddleNode(ListNode *head){
ListNode *slow=head,*fast=head;
while(fast!=nullptr&&fast->next!=nullptr){
fast=fast->next->next;
slow=slow->next;
}
return slow;
}
//将后半部分的结点转置
ListNode* reverseList(ListNode* head){
ListNode *tmp=head,*pre=nullptr,*r=head;
while(r!=nullptr){
r=r->next;
tmp->next=pre;
pre=tmp;
tmp=r;
}
return pre;
}
//判断前后两端是否构成回文链表
bool isPalindrome2(ListNode* head) {
//查找中间结点
ListNode *middleNode=findMiddleNode(head);
//将链表后半部分翻转
ListNode *head2=reverseList(middleNode);
ListNode *p=head2;
while(head2!=nullptr){
if(head->val!=head2->val){
reverseList(p);
return false;
}
head=head->next;
head2=head2->next;
}
reverseList(p);
return true;
}
int main(){
vector<int> a={1,2,2,2,2,2,1};
ListNode *head=createList(a);
ListNode *p=head;
//用于代码调试
while(p!=nullptr){
cout<<p->val<<"->";
p=p->next;
}
cout<<"null\n";
if(isPalindrome2(head)){
cout<<"is Palindrome\n";
}else{
cout<<"is Not Palindrome\n";
}
//用于代码调试
p=head;
while(p!=nullptr){
cout<<p->val<<"->";
p=p->next;
}
cout<<"null\n";
return 0;
}
LeetCode 热题 100_回文链表(24_234)原题链接
欢迎大家和我沟通交流(✿◠‿◠)
原文地址：https://blog.csdn.net/huayimenghan/article/details/143792875
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！