234. 回文链表
难度简单437收藏分享切换为英文关注反馈
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2 输出: false
示例 2:
输入: 1->2->2->1 输出: true
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
通过次数73,751提交次数179,381
步骤：
1.利用快慢指针找出中间点
2.将后半段翻转
3.前段和翻转后的后半段一一对比,若能对上则为回文链表
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverse(ListNode* x,ListNode* y){
if(!y) return x;
ListNode* nex=y->next;
y->next=x;
return reverse(y,nex);
}
bool isPalindrome(ListNode* head) {
ListNode* slow=new ListNode(0);
slow->next=head;
ListNode* fast=slow;
//快慢指针找出中间点
while(fast&&fast->next){
slow=slow->next;//1
fast=fast->next->next;//2
}
//后半段开头节点
ListNode* nex=slow->next;
//结束标志
slow->next=NULL;
/*----------递归法----------*/
// ListNode* head2=reverse(NULL,nex);
/*----------循环法----------*/
ListNode* x=NULL;
ListNode* y=nex;
while(y){
ListNode* nexx=y->next;
y->next=x;
x=y;
y=nexx;
}
//翻转链表头节点
ListNode* head2=x;
//若所有值都一一对应则为循环列表
while(head2){
if((*head).val!=(*head2).val)
return false;
head=head->next;
head2=head2->next;
}
return true;
}
};