方法一:借助数组进行判断
把节点的值复制到一个数组中再利用数组进行判断,但是这样需要占用额外的空间
/**
* Definition for singly-linked list.
* 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) {}
* };
*/
class Solution {
public:
vector<int>tmp;
bool isPalindrome(ListNode* head) {
while(head!=NULL){
tmp.push_back(head->val);
head=head->next;
}
int n=tmp.size();
for(int i=0;i<n/2;i++){
if(tmp[i]!=tmp[n-1-i])
return false;
}
return true;
}
};
方法二:双指针
- 思想:为了使空间复杂度为O(1),将原链表的后半部分反转,然后比较前后两部分每个节点的值是否一样,如果都一样,则这个链表是回文链表,但凡有一个值不一样,就不是回文链表
- 步骤:先找到链表的中间节点,然后把从中间节点的后半部分链表反转,设置两个指针分别指向头指针和中间节点,同时往后遍历并比较每个节点的值进行判断;比较结束要把后半部分链表再反转回来,不要改变初始链表的结果
- 注意:①反转链表要进行两次,可写一个用于反转链表的函数,需要反转链表时直接调用;②利用快慢指针找链表的中间节点时注意循环条件;③将后半部分链表再反转回来时,注意接收返回值时用
pre->next
,不能是pre
.
/**
* Definition for singly-linked list.
* 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) {}
* };
*/
class Solution {
public:
//反转链表的函数
ListNode* reverseList(ListNode*p){
ListNode*pre=NULL;
ListNode*now=p;
while(now!=NULL){
ListNode*next=now->next;
now->next=pre;
pre=now;
now=next;
}
return pre;
}
bool isPalindrome(ListNode* head) {
if(head==NULL || head->next==NULL)
return true;
//找到链表的中间节点
// //方法一:快慢指针法
ListNode*tmp=head,*fast=head,*pre=NULL;
while(fast!=NULL && fast->next!=NULL){
pre=tmp;
tmp=tmp->next;
fast=fast->next->next;
}
//方法二:计算链表长度之后找中间节点
/*ListNode* p=head;
int cnt=0;
while(p!=NULL){
cnt++;
p=p->next;
}
ListNode*tmp=head,*pre=NULL;
for(int i=0;i<cnt/2;i++){
pre=tmp;//最终pre指向的是中间节点的前一个节点,方便最后把链表再反转回来
tmp=tmp->next; //最终tmp指向的是中间节点
}*/
//将链表的后半部分反转
ListNode*mid=reverseList(tmp);
//比较反转后的前后两部分是否每个节点都相同,如果相同,则是回文链表,否则不是
ListNode*first=head;
ListNode*second=mid;
while(second!=NULL){
if(first->val!=second->val)
return false;
first=first->next;
second=second->next;
}
//把后半部分链表再反转回来,使链表与初始状态一样
pre->next=reverseList(mid);
return true;
}
};
标签:head,ListNode,val,next,链表,234,NULL,leetcode
From: https://www.cnblogs.com/cxyupup/p/17338732.html